boj1149 - RGB거리 (python)

문제

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

코드

import sys
input = sys.stdin.readline

n = int(input())
color = [[0,0,0]] + [list(map(int, input().split())) for _ in range(n)]
d = [[0,0,0] for _ in range(n+1)] # 각 집을 R,G,B로 칠한 경우 저장하기 위해 nx3 행렬
# print(color, d)

for i in range(1, n+1):
    d[i][0] = min(d[i-1][1], d[i-1][2]) + color[i][0]
    d[i][1] = min(d[i-1][0], d[i-1][2]) + color[i][1]
    d[i][2] = min(d[i-1][1], d[i-1][0]) + color[i][2]

print(min(d[n]))

설명

dp문제, 각 집에서 색칠할 수 있는 color 중 제일 작은것을 선택하는 것이 아님.
각 집을 R, G, B 로 색칠했을 때의 비용을 모두 저장해놓고 마지막에 최솟값을 선택.

점화식 :
d[i][0] = min(d[i-1][1], d[i-1][2]) + color[i][0]
d[i][1] = min(d[i-1][0], d[i-1][2]) + color[i][1]
d[i][2] = min(d[i-1][1], d[i-1][0]) + color[i][2]

• 참고 : https://m.blog.naver.com/occidere/220785383050