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

Softeer

 

SOLUTION

import sys

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

dp = []
travel_time = [[[0 for i in range(K)] for j in range(K)] for k in range(N)]

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

    for j in range(K):
        for k in range(K):
            if j == k:
                continue

            # 각 작업장 사이를 이동하는 시간들을 전부 할당
            travel_time[i][j][k] = line[K + cnt]
            cnt += 1

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

for i in range(N-1):
    for j in range(K):
        tmp = dp[i][j]
        for k in range(K):
            if j == k: # 같은 번호의 작업장으로 이동할 때는 이동 시간이 안걸리므로 패스
                continue
            
            # min(같은 번호의 작업장으로 이동, 다른 번호의 작업장으로 이동하는 시간 + 작업 시간)
            # 19번째 줄과 다르게 j,k를 반대로 넣어줘야 함
            tmp = min(tmp, dp[i][k] + travel_time[i][k][j]) 
        
        dp[i+1][j] += tmp

print(min(dp[-1]))

진짜 조건과 설명이 너무 불친절한 문제..

Li, j 작업장에서 LK, j+1 (i ≠ K) 작업장으로 이동이 가능(이동시간이 추가됨)할 때 라는 조건을 통해서는

같은 번호의 작업장으로 이동할 수 있는가? 라는 명확한 설명이 나와있지 않다.

 

또한, 이동시간이 추가된다고 했으므로 같은 번호의 작업장으로 이동할 때에는 이동시간이 추가되는지 안되는지

설명을 해줘야 하는게 아닌가 라는 생각이 들었다.

(실제로 문제를 풀때는 같은 번호의 작업장을 이동할 때에는 이동 시간이 걸리지 않는다고 생각하고 풀어야 한다.)

 

다이나믹 프로그래밍(Dynamic Programming)을 이용해 각 작업장마다 걸리는 작업시간을 할당 해준 뒤

3차 배열 travel_time을 이용해 같은 조립라인으로 이동하는것 과 다른 조립라인으로 이동하는 것 중

더 적은 시간을 기존의 dp에 더해 준다. 그 후, 마지막 조립라인의 작업장 중 최솟값을 구해 가장 빠른 조립시간을 구한다.