/////
Search

조립라인

태그
동적계획
체크 필요

문제

동일한 자동차를 생산하는 2개의 조립 라인 A와 B가 있다. 두 조립라인에는 각각 N개의 작업장이 있다. 각각의 작업장을 Ai(1≤i≤N)A_i (1\le i \le N)와 Bi(1≤i≤N)B_i(1\le i \le N)로 표시하자.
AiA_i 작업장과 BiB_i 작업장은 동일한 작업을 수행하지만 작업시간은 다를 수 있다. AA 조립 라인의 경우 A1A_1 작업장에서 최초 조립이 시작되고, AiA_i 작업장에서 작업이 종료되면 바로 Ai+1A_{i+1} 작업장에서 작업을 시작할 수 있다.
BB 조립 라인도 동일한 방식으로 조립을 진행한다. AiA_i 작업장에서 Bi+1B_{i+1} 작업장으로 혹은 BiB_i 작업장에서 Ai+1A_{i+1}작업장으로 반조립 제품의 이동이 가능(이동시간이 추가됨)할 때 자동차 1대의 가장 빠른 조립 시간을 구하여라.

입력

첫 번째 줄에 작업장의 수 NN이 주어진다. i+1(1≤i≤N−1)i+1(1\le i \le N-1) 번째 줄에는 AiA_i 작업장의 작업시간, BiB_i 작업장의 작업시간, AiA_i 작업장에서 Bi+1B_{i+1} 작업장까지 이동시간, BiB_i 작업장에서 Ai+1A_{i+1} 작업장까지 이동시간이 차례로 주어진다. 마지막 N+1N+1 번째 줄에는 ANA_N 작업장과 BNB_N 작업장의 작업시간이 주어진다.
입력은 다음 조건을 만족한다.
•
1≤N≤1031\le N \le 10^3 인 정수
•
각 작업시간과 이동시간은 10510^5를 넘지 않는 양의 정수

출력

첫 번째 줄에 가장 빠른 조립시간을 출력하라.

예시

입력

2 1 3 1 2 10 2
Plain Text
복사

출력

4
Plain Text
복사

정답

import sys N = int(sys.stdin.readline()) A_line = [] # A라인 조립시간 B_line = [] # B라인 조립시간 A_trans = [] # A에서 B로 넘어갈 때 추가 시간 B_trans = [] # B에서 A로 넘어갈 때 추가 시간 for _ in range(N-1): a,b,c,d = list(map(int, sys.stdin.readline().split())) A_line.append(a) B_line.append(b) A_trans.append(c) B_trans.append(d) a, b = list(map(int, sys.stdin.readline().split())) A_line.append(a) B_line.append(b) def fastest(A_line, B_line, A_trans, B_trans): # N = 1인 경우 가장 빠른 것은 각 라인의 첫 원소 중 작은 것. if len(A_line)==1: return min(A_line[0], B_line[0]) # work_a = A_(n-1)까지 걸린 최소 시간 # work_b = B_(n-1)까지 걸린 최소 시간 work_a = 0 work_b = 0 for i in range(len(A_line)-1): time_a = min(work_a + A_line[i], work_b + B_line[i]+B_trans[i]) # A_n 까지 걸리는 최소 시간 = min(work_a + A_(n-1) 조립 시간, work_b + B_(n-1) 조립 시간 + 넘어오는 시간) time_b = min(work_b + B_line[i], work_a + A_line[i]+A_trans[i]) work_a = time_a # work_a 업데이트 work_b = time_b finish_a = work_a + A_line[-1] # A 라인에서 최종으로 끝나는 시간 = work_a + A_line 마지막 원소 finish_b = work_b + B_line[-1] # B 라인에서 최종으로 끝나는 시간 = work_b + B_line 마지막 원소 return min(finish_a, finish_b) # 최소 시간 = min(A 라인에서 끝날 때 최소 시간, B 라인에서 끝날 때 최소 시간) print(fastest(A_line, B_line, A_trans, B_trans))
Python
복사

풀이

•
동적계획으로 푸는 문제이다.
•
우선 A 조립 시간 리스트와 B 조립 시간 리스트 그리고 A에서 B로 넘어가는 이동 시간과 B에서 A로 넘어가는 이동 시간을 담은 리스트를 만들었다.
A_line = [] # A라인 조립시간 B_line = [] # B라인 조립시간 A_trans = [] # A에서 B로 넘어갈 때 추가 시간 B_trans = [] # B에서 A로 넘어갈 때 추가 시간 for _ in range(N-1): a,b,c,d = list(map(int, sys.stdin.readline().split())) A_line.append(a) B_line.append(b) A_trans.append(c) B_trans.append(d) a, b = list(map(int, sys.stdin.readline().split())) A_line.append(a) B_line.append(b)
Python
복사
•
그 다음 N = 1인 경우네는 그냥 각 라인의 첫 원소 중 가장 작은 것을 출력하면 된다.
def fastest(A_line, B_line, A_trans, B_trans): # N = 1인 경우 가장 빠른 것은 각 라인의 첫 원소 중 작은 것. if len(A_line)==1: return min(A_line[0], B_line[0])
Python
복사
•
문제의 포인트는 A_n 까지 또는 B_n 까지 걸리는 최소 시간을 구하는 것이다. 만약 A_n, B_n 까지 걸리는 최소 시간을 구할 수 있다면 A_N, B_N 까지 걸리는 최소 시간을 구할 수 있고 이를 통해서 최소 시간을 구할 수 있기 때문이다. (여기서 A_n까지 걸리는 최소 시간은 A_n의 작업 시간은 제외한다.)
•
그렇다면 A_n 까지 걸리는 최소 시간은 어떻게 구할까?
•
A_n 까지 도달하는 경우는 두 가지가 있다. A_(n-1)에서 직접 내려오는 경우와 B_(n-1)에서 이동시간을 거쳐서 A_(n-1)까지 도달하는 경우.
•
A_(n-1)에서 직접 내려오는 경우 A_(n-1)까지 걸린 최소 시간에 A_(n-1)의 작업 시간을 더해주면 된다.
•
B_(n-1)에서 이동시간을 거쳐서 내려오는 경우 B_(n-1)까지 걸린 최소 시간에 B_(n-1) 작업 시간과 B_(n-1)에서 A_n까지 이동하는 시간을 더해주면 된다.
•
즉 수식으로 써보면
TAn=min⁡(TAn−1+WAn−1,TBn−1+WBn−1+C(Bn−1,An−1))T_{A_n} = \min (T_{A_{n-1}}+W_{A_{n-1}}, T_{B_{n-1}}+W_{B_{n-1}}+C_{(B_{n-1}, A_{n-1})})
TAnT_{A_{n}} 은 AnA_n 까지 걸리는 최소 시간을 의미한다.
WAn−1W_{A_{n-1}} 은 An−1A_{n-1} 에서의 작업시간을 의미한다.
C(Bn−1,An−1)C_{(B_{n-1}, A_{n-1})}은 Bn−1B_{n-1}부터 An−1A_{n-1}까지 이동시간을 의미한다.
•
따라서 이를 ANA_N과 BNB_N까지 계속 반복해서 TANT_{A_N}과 TBNT_{B_N}을 구한다. 그리고 결과적으로 AA 라인에서 끝날 경우 TAN+WANT_{A_N} + W_{A_N} 의 시간이 소요되고 B 라인에서 끝나는 경우 TBN+WBNT_{B_N} + W_{B_N}의 시간이 소요된다. 그리고 총 최소 시간은 min⁡(TAN+WAN,TBN+WBN)\min (T_{A_N}+W_{A_N}, T_{B_N}+W_{B_N})이다.
# work_a = A_(n-1)까지 걸린 최소 시간 # work_b = B_(n-1)까지 걸린 최소 시간 work_a = 0 work_b = 0 for i in range(len(A_line)-1): time_a = min(work_a + A_line[i], work_b + B_line[i]+B_trans[i]) # A_n 까지 걸리는 최소 시간 = min(work_a + A_(n-1) 조립 시간, work_b + B_(n-1) 조립 시간 + 넘어오는 시간) time_b = min(work_b + B_line[i], work_a + A_line[i]+A_trans[i]) work_a = time_a # work_a 업데이트 work_b = time_b finish_a = work_a + A_line[-1] # A 라인에서 최종으로 끝나는 시간 = work_a + A_line 마지막 원소 finish_b = work_b + B_line[-1] # B 라인에서 최종으로 끝나는 시간 = work_b + B_line 마지막 원소 return min(finish_a, finish_b) # 최소 시간 = min(A 라인에서 끝날 때 최소 시간, B 라인에서 끝날 때 최소 시간)
Python
복사