[Level3] 조립라인

조립라인 문제 링크

🌟문제

동일한 자동차를 생산하는 2개의 조립 라인 A와 B가 있다. 두 조립라인에는 각각 N개의 작업장이 있다. 각각의 작업장을 Ai (1 ≤ i ≤ N)와 Bi (1 ≤ i ≤ N)로 표시하자. Ai 작업장과 Bi 작업장은 동일한 작업을 수행하지만 작업시간은 다를 수 있다. A 조립 라인의 경우 A1 작업장에서 최초 조립이 시작되고, Ai 작업장에서 작업이 종료되면 바로 Ai+1 작업장에서 작업을 시작할 수 있다.
B 조립 라인도 동일한 방식으로 조립을 진행한다. Ai 작업장에서 Bi+1작업장으로 혹은 Bi 작업장에서 Ai+1작업장으로 반조립 제품의 이동이 가능(이동시간이 추가됨)할 때 자동차 1대의 가장 빠른 조립 시간을 구하여라.

DP를 이용해서 문제를 풀었고, 알고리즘이 정말 완벽하다고 생각했는데 자꾸 테스트 케이스에서 에러가 나서 애먹은 문제...😥

구글링했더니 처음부터 끝까지 나랑 똑같이 푸신 분이 있었는데, 딱 한 코드의 차이가 있었다.

📑 알고리즘

dp[i]은 [Ai까지 오는 경로의 최솟값, Bi까지 오는 경로의 최솟값]으로 이루어져 있다.
예를 들어 dp[i][0]은 Ai까지 오는 경로의 최솟값인데,

• 1. Ai-1에서 바로 Ai로 내려오는 경로 (A → A)
• 2. Bi-1에서 조립라인을 바꿔 Ai로 내려오는 경로 (B → A)

이렇게 두개의 경로가 존재한다. 두개의 경로중에 min값을 취하고, 거기에 현재 Ai에서 작업한 시간을 더해주면 dp[i][0]의 최솟값을 구할 수 있다.
여기서 2번의 경우에는 이동시간까지 고려해서 더해주기만 하면 된다!

dp[i][1]도 똑같은 방법으로 구해서 넣어주면 된다.

😠 코드 리뷰

dp = [[0,0]]*n

for i in range(1,n):
    #틀린코드
    dp[i][0] = min(dp[i-1][0],dp[i-1][1]+arr[i-1][3])+arr[i][0]
    dp[i][1] = min(dp[i-1][1],dp[i-1][0]+arr[i-1][2])+arr[i][1]
    
    #맞는코드
    #dp[i] = [min(dp[i-1][0],dp[i-1][1]+arr[i-1][3])+arr[i][0], min(dp[i-1][1],dp[i-1][0]+arr[i-1][2])+arr[i][1]]

먼저 dp를 2차원 리스트로 선언해주고, for문을 돌때 점화식을 세워 각 원소에 넣어주는 코드를 짰는데, 여기서 문제가 생겼던 것 같다.

2차원 리스트 에러 해결

❗이 문제가 왜 발생하는지 찾아보니 연산자를 사용하면서 참조를 복사하는 것이 에러가 발생 한다는 것 이었다.

dp[1][1] 원소의 값만 넣어줬는데, 결과는 모든 dp[x][1]의 값이 3으로 바뀐 것을 알 수 있다.

이런 식으로 리스트의 선언을 바꿔주면 내가 바꾸자하는 원소의 값만 바꿀 수 있다.

😊 전체 코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0,0] for _ in range(n)]

arr = []
for _ in range(n):
    arr.append(list(map(int,input().split())))
dp[0] = [arr[0][0],arr[0][1]]

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

print(min(dp[-1]))