백준 1149 - RGB 거리

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

1149번: RGB거리

 

---

풀이 과정

d[i][k]를 총 i개의 집을 조건에 맞게 칠하는 비용의 최소값이되 마지막이 k로 칠해지는 경우라고 하자. (0 = 빨강, 1 = 초록, 2 = 파랑)

 

그러면 다음과 같은 점화식이 성립한다.

d[i][0] = min(d[i-1][1], d[i-1][2]) + p[i][0]

d[i][1] = min(d[i-1][0], d[i-1][2]) + p[i][1]

d[i][2] = min(d[i-1][0], d[i-1][1]) + p[i][2]

---

소스 코드

import sys

N = int(sys.stdin.readline())
d = [[0 for _ in range(4)] for _ in range(N+1)]
p = [[0, 0, 0]]

for i in range(1, N+1):
    p.append(list(map(int, sys.stdin.readline().split())))
    d[i] = p[i]
    d[i][0] = min(d[i - 1][1], d[i - 1][2]) + p[i][0]
    d[i][1] = min(d[i - 1][0], d[i - 1][2]) + p[i][1]
    d[i][2] = min(d[i - 1][0], d[i - 1][1]) + p[i][2]

print(min(d[N]))