RGB거리 - 1149번

다이나믹프로그래밍으로 문제를 풀면 된다.

각 단계별로 전체 색에대한 최소값을 구하려다 실패하였다.

 

각 단계별로, 각 색에대해 최소값을 구한 뒤, 마지막에 최소값을 구해주면 문제를 해결할 수 있다.

 

예제

3

26    40    83

49    60    57

13    89    99

 

->

26    40    83

89    86    83

96    172  185

최소값 : 96

 

 

import sys
n = int(sys.stdin.readline())
house = [[] for i in range(n+1)]

for i in range(n):
    house[i+1] = list(map(int, sys.stdin.readline().split()))
cost = house.copy()
for i in range(2,n+1):
    cost[i][0] += min(cost[i-1][1],cost[i-1][2])
    cost[i][1] += min(cost[i-1][0],cost[i-1][2])
    cost[i][2] += min(cost[i-1][1],cost[i-1][0])
print(min(cost[n]))