[Softeer] 조립라인

문제

요약

A와 B, 두 개의 조립라인이 있고,
A1 -> A2 이렇게 이동하거나 A1->B2 이렇게 i에서 i+1로 라인을 이동할 수 있는데

다른 조립라인으로 이동할 때는 추가적인 이동시간이 걸린다.

가장 빠른 조립라인의 시간을 구하여라.

 

원본

https://softeer.ai/practice/6287

Softeer - 현대자동차그룹 SW인재확보플랫폼

풀이

풀이1(시간초과 및 오답)

처음 재귀로 접근했을때, 예시 테스트 케이스만 맞고 두개는 오답, 두개는 시간초과가 떴다.

시간초과는 예상 했는데 오답인 부분은 어디서 오답이 발생하는 지 모르겠다.  

import sys
input = sys.stdin.readline

n = int(input())
arr, AB = [[0]*n for _ in range(2)], [[0] * n for _ in range(2)]
for i in range(n-1):
    arr[0][i], arr[1][i], AB[0][i+1], AB[1][i+1] = map(int, input().split())
arr[0][n-1], arr[1][n-1] = map(int, input().split())

answer = 999999999

def sol(now, i, idx):
    global answer
    
    if now > answer:
        return

    if idx == n:
        answer = min(answer, now)
        return

    sol(now+arr[i][idx], i, idx+1)
    sol(now+arr[i][idx]+AB[i][idx], i-1 if i else i+1, idx+1) 
    
sol(arr[0][0], 0, 0)
sol(arr[1][0], 1, 0)
print(answer)

 

 

 

풀이2(정답)

빠르거나 가장 긴 루트를 찾을 때 재귀보다 시간을 줄이려면 DP다.

처음 접근할 때는 앞에서부터 뒤에것을 더해갔다면

dp로 풀때는 현재에 앞에서 가장 적은 것을 더해간다.

 

import sys
input = sys.stdin.readline

n = int(input())
arr, AB = [[0, 0] for _ in range(n)], [[0, 0] for _ in range(n)]
for i in range(n-1):
    arr[i][0], arr[i][1], AB[i+1][0], AB[i+1][1] = map(int, input().split())
arr[n-1][0], arr[n-1][1] = map(int, input().split())

dp = [[0, 0] for _ in range(n)]
dp[0][0], dp[0][1] = arr[0][0], arr[0][1]

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

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