[Softeer/Python] 복잡한 조립라인2 ★★★★★ - 효과는 굉장했다!

Softeer

 

 

SOLUTION

 

실패한 코드

import sys

K, N = map(int, sys.stdin.readline().split())

dp = []
travel_time = []

for i in range(N-1):
    line = list(map(int, sys.stdin.readline().split()))
    dp.append(line[:K])
    travel_time.append(line[-1])

dp.append(list(map(int, sys.stdin.readline().split())))

for i in range(N-1):
    for j in range(K):
        if i == j:
            dp[i+1][j] += dp[i][j]

        else:
            dp[i+1][j] += min(dp[i][j], min(dp[i]) + travel_time[i])

print(min(dp[-1]))

 

성공한 코드

import sys

K, N = map(int, sys.stdin.readline().split())

dp = []
travel_time = []

for i in range(N-1):
    line = list(map(int, sys.stdin.readline().split()))
    dp.append(line[:K]) # 작업 시간
    travel_time.append(line[-1])

# 마지막 라인에는 이동시간이 없으므로 따로 추가   
dp.append(list(map(int, sys.stdin.readline().split())))

for i in range(N-1):
    # 이동시간이 전부 같으므로 계속 최소시간이 걸리는 작업장을 찾아서 진행한다
    tmp = min(dp[i]) 

    for j in range(K):
        if i == j:
            dp[i+1][j] += dp[i][j]

        else:
            dp[i+1][j] += min(dp[i][j], tmp + travel_time[i])

print(min(dp[-1]))

이동시간이 전부 같기 때문에 처음 문제를 풀 때 이중 for 문을 이용해 단순히 구하면되겠구나 라고 생각했다.

그러나 문제의 조건을 보면 1 ≤ N ≤ 10^2 인 정수, 1 ≤ K ≤ 10^4 인 정수 이기 때문에 실패한 코드처럼

else 문 안에서 min(dp[i])를 구하면 시간 복잡도가 O(NK^2) 되므로 시간 초과가 나게된다.

 

이를 해결하기 위해 for 문이 도는 동시에 min(dp[i])를 같이 구해준다면 시간 복잡도를 O(NK) 로 줄일 수 있고,

시간 초과 없이 문제를 해결 할 수 있다.