import sys
K,N = map(int, sys.stdin.readline().split())
dp = [[1000000000 for i in range(K)] for j in range(N)]
dists = [[[0 for i in range(K)] for j in range(K)] for k in range(N)]
values = [[0 for i in range(K)] for j in range(N)]
동적프로그래밍을 위한 리스트 (dp), 거리 담을 리스트 (dists), 그리고 각 작업장 각 조립라인 별 걸리는 작업 시간 (values)을 담을 리스트를 각각 준비해준다. (여기서 dp에 모든 값을 10000000000이라는 큰 수로 초기화해주었는데, 이는 이따가 진행할 동적프로그래밍은 최소화 연산이기 때문에 가능한 큰 값을 넣어 최소화 갱신에 문제가 안생기도록 하기 위함이다. -> 예를 들어 0으로 초기화해준다면 나중에 동적프로그래밍을 모두 마치고 나서도 dp가 0으로 유지되는 불상사가 생길 수 있다.)
# 방법 1
dists = [[[0]*K]*K]*N]
# 방법 2
dists = [[[0 for i in range(K)] for j in range(K)] for k in range(N)]
여기서 유의할 점은 방법 1로 이를 만들어선 절!대! 안된다는 것이다. 방법 1로 하게 되면 마지막에 *N이라는 부호는 결국 [[0]*K]*K] 라는 리스트를 N번 복사한 것을 의미하며, 이 경우 그중 하나 [[[0]*K]*K] 을 골라 갱신하게 되면 N개의 모든 리스트값이 갱신되게 된다. 그렇기에 for 루프를 통해 리스트를 갱신해주는 습관을 들이는게 가장 좋다.
그렇게 모든 준비를 마쳤다.
Step 1. 받아들이는 입력값을 편하게 정리
우리는 0번에 나온 것과 같은 입력값을 받아들였을 때, 이를 가치값과 거리값(이동시간)으로 각각 담아줄 필요가 있다. 다만 거리에 있어서는 같은 작업장으로 이동할 경우는 거리값이 0이기 때문에 0을 담아주고, 나머지 행렬에 거리 값을 순서대로 넣어줄 필요가 있다.
이를 위해 일단 거리를 담을 수 있도록 i와 j로 돌리는 이중 루프를 짜고, dists[i][j]에 다른 또 하나의 카운트 변수 count를 넣어 실현한다. 위와 같이 실현할 경우 i와 j가 같을 경우에는 거리값을 갱신하는 과정을 스킵하게 되고, count 또한 그대로 남아 있게 되며, i와 j가 같지 않을 경우에만 거리 값을 갱신할 수 있게 된다.
그리고 나서 i와 j 루프를 이용해서 values (각 조립 라인 별 작업 시간) 값에 작업시간 L을 하나하나 담아준다.
그리고 마지막 인풋은 작업장 시간만 들어오기 때문에 이를 위한 루프를 따로 만들어줘 데이터를 받아준다.
여기까지 입력값을 사용하기 편하도록 깔끔하게 정리했다.
Step 2. 규칙 파악
규칙을 파악하면 되게 간단하다. 다음(i+1) 작업장에서 j번째 조립라인을 마치는데 걸리는 최소 시간은 앞선 작업장(i)에서의 "조립라인에서 걸리는 작업시간 + 이동시간"의 최소값에다가 i+1 작업장에서 j번째 조립라인을 마치는데 걸리는 작업 시간이 되기 때문이다.
규칙을 파악했으니 이제 동적프로그래밍을 통해 코드를 짜보자.
Step 3. 동적프로그래밍
# 동적 프로그래밍
for i in range(N-1):
for j in range(K):
for k in range(K):
dp[i+1][j] = min(dp[i+1][j], dp[i][k]+dists[i][k][j])
dp[i+1][j] += values[i+1][j]
모든 작업장을 위해 루프를 하나 설정하고(i), 동적프로그래밍 연산을 위해 모든 조립라인을 2번씩 루프(j, k)를 돌리며 "이전 작업장에서의 조립시간 + 이동 시간"의 최소값을 그 다음 작업장에 갱신시키는 과정을 계속 반복한다. 그렇게 되면 가능한한 모든 경우의 수를 계산하며 각각 작업장에서 걸리는 최소값을 연산할 수가 있게 된다.
코드
import sys
K,N = map(int, sys.stdin.readline().split())
dp = [[1000000000 for i in range(K)] for j in range(N)]
dists = [[[0 for i in range(K)] for j in range(K)] for k in range(N)]
values = [[0 for i in range(K)] for j in range(N)]
# 데이터 깔끔하게 정리
for i in range(N-1):
data_proc = list(map(int, sys.stdin.readline().split()))
# 거리 데이터 깔끔하게 정리
for j in range(K):
cnt = 0
for k in range(K):
if (j!=k):
dists[i][j][k] = data_proc[K+(K-1)*j+cnt]
cnt += 1
values[i][j] = data_proc[j]
# 마지막 작업장 소모시간 저장
values[N-1] = list(map(int, sys.stdin.readline().split()))
# 초기값 세팅
for i in range(K):
dp[0][i]=values[0][i]
# 동적 프로그래밍
for i in range(N-1):
for j in range(K):
for k in range(K):
dp[i+1][j] = min(dp[i+1][j], dp[i][k]+dists[i][k][j])
dp[i+1][j] += values[i+1][j]
print(min(dp[N-1]))
