[백준]1149번 RGB거리 - DP

 

n = int(input())

cost = []
for i in range(n):
    cost.append(list(map(int, input().split())))

for i in range(1, n):
    cost[i][0] += min(cost[i-1][1], cost[i-1][2]) # 선택할 수 있는 i-1(이전 값)에서 작은 것을 누적시켜 더함
    cost[i][1] += min(cost[i-1][0], cost[i-1][2])
    cost[i][2] += min(cost[i-1][0], cost[i-1][1])


print(min(cost[-1]))

 

 코드 설명

각 집을 RGB로 칠하는 비용을 먼저 리스트에 저장한다. 그 후 반복문을 돌면서 R, G, B 각각 칠하는 비용을 누적시켜 구한다.

마지막에 저장된 값중 최솟값을 통해 정답을 구할 수 있다.

 

Point : 각 집을 R G B 로 칠하는 3가지의 경우를 모두 구한다. R을 고를 경우에는 G와 B만 칠할 수 있고, G의 경우에는 R과 B, B의 경우에는 R, G를 칠할 수 있다. 이점을 이용하여 전 단계중에서 더 적은 비용을 칠할 수 있는 값을 누적시켜 더한다.

즉, i 번째의 집을 R G B 3가지로 칠하는 경우의 값을 구할 수 있게 된다.