[백준] RGB거리

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

1149번: RGB거리

다이나믹 프로그래밍을 이용하는 문제입니다.

 

우선 문제부터 간단히 요약해보면, 

N개의 집들을 R, G, B 이렇게 세가지 색으로 색칠해야 하는데 이웃한 두 집들은 색이 달라야 합니다. 이 때, 각각의 집들을 각각의 색으로 색칠할 때 드는 비용이 주어집니다. 이 때, 모든 집들을 색칠할 때 드는 비용의 최솟값을 구하는 것이 문제입니다. 

 

실제로 문제에서는 조건을 복잡하게 주기는 하지만 요약해보면 위와 같은 이야기입니다. 

점화식을 세워서 풀면 간단하게 해결 할 수 있습니다. 

 

<Solution>

간단한 예시로 설명해보겠습니다. 

 

이렇게 각각 R, G, B에 대한 dp Table을 구성한 뒤 최종적으로 min(R[n], G[n], B[n]) 을 구하면 이것이 정답이 됩니다.

 

실제 구현은 아래와 같습니다. 

import sys

N = int(sys.stdin.readline().rstrip())

cost = [[]]
for i in range(N):
    cost.append(list(map(int,sys.stdin.readline().rstrip().split())))

dp_R = [0] * (N+1)
dp_G = [0] * (N+1)
dp_B = [0] * (N+1)

dp_R[1] = cost[1][0]
dp_G[1] = cost[1][1]
dp_B[1] = cost[1][2]

for i in range(2,N+1):
    dp_R[i] = min(dp_G[i-1] + cost[i][0], dp_B[i-1] + cost[i][0])
    dp_G[i] = min(dp_R[i-1] + cost[i][1], dp_B[i-1] + cost[i][1])
    dp_B[i] = min(dp_G[i-1] + cost[i][2], dp_R[i-1] + cost[i][2])

print(min(dp_R[N], dp_G[N], dp_B[N]))