이 문제의 본질은 동적프로그래밍이며, 더욱 구체적으로 말하자면 우선 이 문제에서 나타나는 규칙을 알아야 하고, 그 규칙을 수학적으로 떠올려보고, 이 수학식을 코드로 작성하면 된다.
입력예제1 2 1 3 1 2 10 2
입력 예제를 예로 보면, 2개의 작업장이 있고, A0, B0에서 1과 3이라는 시간이 걸리며, A0에서 B1로 이동하는데 걸리는 시간은 1, B0에서 A1로 이동하는데 걸리는 시간은 2이다.
그럼 첫번째 작업장에서 걸린 시간은 A 작업장에서는 A0 만큼의 시간이 걸렸을 것이고, B 작업장에선 B0만큼의 시간이 걸렸을 것이다.
그럼 두번째 작업장으로 이동했을 때 걸리는 시간을 따져보면,
두번째 작업장에서 A작업장에서 일을 마쳤을 때의 최소 시간을 따져보면 "A0"와 "B0+이동시간" 중의 최소값에 A1만큼의 시간을 더해준 값이 될 것이며, 마찬가지로 B작업장에서의 일을 마쳤을 때의 최소 시간을 따져보면 "B0"과 "A0+이동시간" 중의 최소값에 B1을 더해준 값이 될 것이다. (그 이유는 모든 작업장을 최소로 끝내는 시간은 결국 이전의 한 작업장 한 작업장을 최소한의 시간으로 끝냈을 때의 결과물이 될 것이기 때문이다.)
이를 표현해주면 위와 같은 행렬의 방식으로 표현이 가능하다. 그럼 이를 코드로 작성해보면 아래와 같다. 그리고 마지막 최종 결과물은 행렬의 아주 가장 밑바닥에 있는 값들 중 최소값을 출력하면 된다.
코드
import sys
N = int(input())
values = [[0,0] for _ in range(N)]
for i in range(0, N-1):
Ai, Bi, dAi, dBi = list(map(int, sys.stdin.readline().split()))
values[i][0] += Ai
values[i][1] += Bi
values[i+1][0] = min(values[i][0], values[i][1]+dBi)
values[i+1][1] = min(values[i][1], values[i][0]+dAi)
last_A, last_B = map(int, sys.stdin.readline().split())
values[N-1][0] = values[N-1][0]+last_A
values[N-1][1] = values[N-1][1]+last_B
print(min(values[N-1]))
