[Python/백준] RGB 거리

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

 

참고

https://m.blog.naver.com/occidere/220785383050

[백준] 1149 - RGB거리 (2017-12-02 수정완료)

 

---

dp를 사용하기 위해 점화식을 만든다

현재 집의 R, G, B를 선택했을 때의 최솟값을 선택한다

R이 0번 인덱스, G가 1번 인덱스, B가 2번 인덱스일 때

현재 -1 집의 인덱스가 겹치지 않도록 점화식을 만든다

 

현재집에 R을 선택했을 때 -> R 선택 비용 + 현재-1집의 G, B 중 최소 비용

dp[i][0] = lists[i][0] + min(lists[i-1][1], lists[i-1][2])

 

현재집에 G를 선택했을 때 -> G 선택 비용 + 현재-1집의 R, B 중 최소 비용

dp[i][1] = lists[i][1] + min(lists[i-1][0], lists[i-1][2])

 

현재집에 B을 선택했을 때 -> B 선택 비용 + 현재-1집의 R, G 중 최소 비용

dp[i][2] = lists[i][2] + min(lists[i-1][0], lists[i-1][1])

 

 

import sys
input = sys.stdin.readline

n = int(input())

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