문제

동일한 자동차를 생산하는 2개의 조립 라인 A와 B가 있다. 두 조립라인에는 각각 N개의 작업장이 있다. 각각의 작업장을 $A_i$ (1 ≤ i ≤ N)와 Bi (1 ≤ i ≤ N)로 표시하자. $A_i$ 작업장과 $B_i$ 작업장은 동일한 작업을 수행하지만 작업시간은 다를 수 있다. A 조립 라인의 경우 $A_1$ 작업장에서 최초 조립이 시작되고, $A_i$ 작업장에서 작업이 종료되면 바로 $A_{i+1}$ 작업장에서 작업을 시작할 수 있다.

B 조립 라인도 동일한 방식으로 조립을 진행한다. $A_i$ 작업장에서 $B_{i+1}$작업장으로 혹은 $B_i$ 작업장에서 $A_{i+1}$작업장으로 반조립 제품의 이동이 가능(이동시간이 추가됨)할 때 자동차 1대의 가장 빠른 조립 시간을 구하여라.

풀이

아이디어

• 언뜻봐서는 DFS로 계속 최소값을 갱신시켜나가야 하는 것처럼 보이지만, N의 최댓값이 1000이다. 다른 문제 같았으면 1000쯤이야 작은 숫자지만 DFS로..? 한다면 완전 시간초과 100%이다.
• DFS인데 숫자가 크면 => DP로 생각해보자!
• 점화식을 세워보면 다음과 같다.

DP[i][j] = min(DP[i-1][j] + worktime[i][j], DP[i-1][1-j] + movetime[i-1][1-j] + worktime[i][j])

즉, 현재 단계에서의 최소 코스트는

1. 이전단계의 같은조립라인에서의 최소코스트 + 현재 작업코스트
2. 이전단계의 다른조립라인에서의 최소코스트 + 현재 작업코스트 + 조립라인변경시간

이 둘 중에 하나이다.

코드

import sys
N = int(sys.stdin.readline()) #작업장의 수

#movetime[i][j] = i단계에서 i+1단계로 갈 때 a->b 또는 b->a로 갈아타는 시간
movetime = []

#worktime[i][j] = i단계에서 각 단계에서 소요되는 시간
worktime = []

for i in range(N-1):
  wa, wb, ma, mb = map(int, sys.stdin.readline().split(' '))
  worktime.append([wa, wb])
  movetime.append([ma, mb])

wa, wb = map(int, sys.stdin.readline().split(' '))
worktime.append([wa, wb])

# DP 시작
wa, wb = worktime[0]
DP = [[0]*2 for _ in range(N)]
DP[0] = [wa, wb]

# 규칙
# DP[i][j] = i번째 단계의 j작업장까지 왔을 때 걸린 최소 시간
# DP[i][0] = min(DP[i-1][0], DP[i-1][1] + movetime[i-1][1])
# DP[i][1] = min(DP[i-1][1], DP[i-1][0] + movetime[i-1][0])
for i in range(1, N):
  for j in range(2):
    DP[i][j] = min(DP[i-1][j] + worktime[i][j], DP[i-1][1-j] + movetime[i-1][1-j] + worktime[i][j])

print(min(DP[N-1][0], DP[N-1][1]))