백준 1149번: RGB 거리 (Python)

접근

[0, 0, 0] 리스트 N + 1개를 요소로 갖는 리스트(코드에서는 min_price)를 작성하여, 각 요소를 다음과 같은 의미를 갖도록 채운다.

• min_price[i][j] = i 번째 집에 j를 선택했을 때 채색 비용의 최소값

즉, min_price[10][0] 요소는 10번째 집에 R 색을 선택했을 때의 채색 최소값을 가지게 된다. 이는 다음의 점화식을 통해 구현할 수 있다.

min_price[i][0] = min(min_price[i - 1][1], min_price[i - 1][2]) + price[i][0]  # price는 해당 집 하나를 채색하는 비용 리스트
min_price[i][1] = min(min_price[i - 1][0], min_price[i - 1][2]) + price[i][1]
min_price[i][2] = min(min_price[i - 1][0], min_price[i - 1][1]) + price[i][2]

코드

import sys


n = int(sys.stdin.readline())
price = [[0, 0, 0]]
for i in range(n):
    r, g, b = map(int, sys.stdin.readline().split())
    price.append([r, g, b])
min_price = []
min_price.append([0, 0, 0])
for j in range(1, n + 1):
    temp0 = min(min_price[j - 1][1], min_price[j - 1][2]) + price[j][0]
    temp1 = min(min_price[j - 1][0], min_price[j - 1][2]) + price[j][1]
    temp2 = min(min_price[j - 1][0], min_price[j - 1][1]) + price[j][2]
    min_price.append([temp0, temp1, temp2])
print(min(min_price[n]))

더 생각해 볼 것?

...