문제 링크

문제 설명

input

work_time

작업장 번호에 따른 작업 소요 시간 리스트

[ [A0,B0],[A1,B1],[A2,B2],...,[An-1,Bn-1] ]

문제에서는 1번 작업장부터 나오지만 나는 파이썬 언어적 특성을 반영하여 0번부터 시작했다.

2번 작업장의 소요 시간은
A 라인 : A2
B 라인 : B2 이다.

move_time

라인 A --> B OR B --> A 로 이동 소요 시간 리스트

[ [A0,B0],[A1,B1],[A2,B2],...,[An-1,Bn-1] ]

2번 작업장-->3번 작업장의 이동 시간은
A-->B : A2
B-->A : B2

output

min(dp_a[N-1],dp_b[N-1])

dp_a[i]와 dp_b[i]는 각 라인에서 i번째 작업장에서의 최소 소요 시간을 의미한다.

따라서 A/B 라인에서 마지막 작업장의 최소 소요시간을 구한 후, 둘 중에 더 최소값이 답이다.

Algorithm

DP

Dynamic Programming을 사용했다.

dp[i]와 dp[i-1]의 점화식을 구하여 memoization으로 풀었다.

설계

1

# i번째 작업장에서 최소 시간
dp_a = [work_time[0][0]]*N # A 라인
dp_b = [work_time[0][1]]*N # B 라인

DP 배열 초기화

2

for i in range(1,N):
    a,b = work_time[i]
    a_move,b_move = move_time[i-1]

    dp_a[i] = min(dp_a[i-1] + a, dp_b[i-1] + b_move + a)
    dp_b[i] = min(dp_a[i-1] + a_move + b, dp_b[i-1] + b)

print(min(dp_a[N-1],dp_b[N-1]))

i 작업장 최소시간 =

• i-1 작업장 최소시간 + i 작업장 소요시간 : 라인 이동 X
• i-1 작업장 최소시간 + 이동 시간 + i 작업장 소요시간: 라인 이동 O

둘 중에 더 작은 거

코드

import sys
input = sys.stdin.readline

N = int(input())
work_time = []
move_time = []
for i in range(N-1):
    a,b,a_move,b_move = map(int,input().split())
    work_time.append([a,b])
    move_time.append([a_move,b_move])
work_time.append(list(map(int,input().split())))

# i번째 작업장에서 최소 시간
dp_a = [work_time[0][0]]*N # A 라인
dp_b = [work_time[0][1]]*N # B 라인

for i in range(1,N):
    a,b = work_time[i]
    a_move,b_move = move_time[i-1]

    dp_a[i] = min(dp_a[i-1] + a, dp_b[i-1] + b_move + a)
    dp_b[i] = min(dp_a[i-1] + a_move + b, dp_b[i-1] + b)

print(min(dp_a[N-1],dp_b[N-1]))