Softeer 조립라인 (난이도 3)

정답 코드

import sys
INPUT = sys.stdin.readline
N = int(INPUT())
lines = [[0, 0, 0, 0] for i in range(N)]

for i in range(N - 1):
    lines[i][0], lines[i][1], lines[i][2], lines[i][3] = map(int, INPUT().split())
lines[N - 1][0], lines[N - 1][1] = map(int, INPUT().split())

dp = [[0, 0] for i in range(N)]
dp[0][0] = lines[0][0]
dp[0][1] = lines[0][1]
for i in range(1, N):
    dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + lines[i - 1][3]) + lines[i][0]
    dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + lines[i - 1][2]) + lines[i][1]

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

알고리즘 유형

dynamic programming

후기

백준에서 비슷한 문제를 여럿 봤어서 빨리 풀었다.