Softeer 복잡한 조립라인2 (난이도 5)

정답 코드

import sys
K, N = map(int, sys.stdin.readline().split())
L = []

for i in range(N):
    L.append(list(map(int, sys.stdin.readline().split())))

dp = [[0 for i in range(K)] for j in range(N)]
minV = [[10000000, 0] for i in range(N)]
for i in range(K):
    dp[0][i] = L[0][i]
    if minV[0][0] > dp[0][i]:
        minV[0][0] = dp[0][i]
        minV[0][1] = i

for i in range(1, N):
    for j in range(K):
        if minV[i - 1][1] == j:
            dp[i][j] = minV[i - 1][0] + L[i][j]
        else:
            dp[i][j] = min(dp[i - 1][j], minV[i - 1][0] + L[i - 1][K]) + L[i][j]
        if minV[i][0] > dp[i][j]:
            minV[i][0] = dp[i][j]
            minV[i][1] = j

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

문제 유형

dynamic programming

후기

O(K^2 * N)만큼 걸리게 했더니 시간 초과 문제가 생겨 dp의 row 중 가장 작은 값을 기록하면서 풀었다.