[백준 #1149] RGB거리(Python)

https://www.acmicpc.net/problem/1149

1149번: RGB거리

dp[i][0] = R

dp[i][1] = G

dp[i][2] = B

26	40	83
49+min(40,83)=89	60+min(26,83)=86	57+min(26,40)=83
13+min(86,83)=96	89+min(89,83)=172	99+min(89,86)=185

dp에는 계속 최저 비용을 저장한다.

빨강으로 칠할 경우, 그전 집은 파랑이나 초록으로 칠해야 하므로 그중 더 적은 비용을 더하여 업데이트하는 방식이다.

 

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][0], dp[i - 1][1]) + dp[i][2]
print(min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]))