[Softeer]조립라인 파이썬 풀이

Softeer 조립라인¶

문제 page: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=403

알고리즘 문제에서 가장 많은 or 적은, 가장 빠른 or 빠른등과 같은 문제는 dynamic programming(dp)문제가 많은 것 같다.
조립라인도 dp를 통해서 풀 수 있다.
조립라인의 핵심은 A에서 조립하는 경우와 B에서 조립하는 경우를 분리해야 하는 점이다.
즉 A에서 조립할 때 최소 시간, B에서 조립할 때 최소 시간을 bottom-up방식으로 계속 구해준 후 마지막 결과값으로 어느 작업장에서 조립할 때 최소 시간을 갖는지 구해주면 된다.
A작업장의 i번째 경우를 예로 들어보면

1) A[i-1]에서 작업한 최소시간
2) B[i-1]에서 작업한 최소시간 + B에서 A까지 이동 시간
1)과 2)를 비교한 후
3) A[i]의 작업시간을 더해주면 된다.

마찬가지로 B작업장의 i번째 경우도 갱신해준다.
그러면 최종 결과값은 다음과 같이 이루어질 것이다.
[$A_{n}$작업장에서 작업을 끝마칠 때 최소시간, $B_{n}$작업장에서 작업을 끝마칠 때 최소시간]

In [ ]:

N = int(input())
work_time = [ [], [] ]
move_time = [ [], [] ]
for _ in range(N-1):
    A, B, A_B, B_A = [int(x) for x in input().split()]
    work_time[0].append(A)
    work_time[1].append(B)
    move_time[0].append(A_B)
    move_time[1].append(B_A)
A, B = [int(x) for x in input().split()]
work_time[0].append(A)
work_time[1].append(B)

dp = [[work_time[0][0]], [work_time[1][0]]]


for i in range(1, N):
    dp[0].append(min(dp[0][i-1], dp[1][i-1]+move_time[1][i-1]) + work_time[0][i])
    dp[1].append(min(dp[1][i-1], dp[0][i-1]+move_time[0][i-1]) + work_time[1][i])

print(min(dp[0][-1], dp[1][-1]))