백준 (python 파이썬) 1149 RGB거리

백준 링크:https://www.acmicpc.net/problem/1149

1149번: RGB거리

1번집의 최솟값을 구하고 계산을 해서 틀려버린 문제였다.

 

오답 코드

tc=int(input())
dp=[]
swich=[True,True,True]
for i in range(tc):
    order=list(map(int,input().split()))
    if False in swich:
        order[swich.index(False)] = 1001
    if len(dp) == 0:
        dp.append(min(order))
        swich[order.index(min(order))] = False
    else:
        swich[swich.index(False)] = True
        dp.append(min(order))
        swich[order.index(min(order))] = False
print(sum(dp))

이렇게 하면 나머지 DP[0][1], DP[0][2]의 경우를 무시해서 오답이 나버린다.

 

 

정답 코드

n=int(input())
dp=[]
for i in range(n):
    dp.append(list(map(int,input().split())))
for i in range(1,len(dp)):
    dp[i][0] = min(dp[i-1][1],dp[i-1][2])+dp[i][0]
    dp[i][1] = min(dp[i-1][0],dp[i-1][2])+dp[i][1]
    dp[i][2] = min(dp[i-1][1],dp[i-1][0])+dp[i][2]
print(min(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

[0]일때는 DP[i-1][1] or [2]+ DP[i][0]를 더해가며 계산하면 된다.

[1] = DP[i][1] + DP[i-1][0] or [2] 

2도 마찬가지다

그리고 계산이 끝난 dp의 리스트중 가장 작은수를 출력하면 끝!

 

나는 멍청해서 한시간 넘게걸림..