[BOJ] 1149 - RGB거리

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

1149번: RGB거리

import sys
n = int(sys.stdin.readline())
graph = []
for _ in range(n):
    data = list(map(int, sys.stdin.readline().rstrip().split()))
    graph.append(data)

dp = [[0] * 3 for _ in range(n)]
dp[0] = graph[0]

for i in range(1, n):
    dp[i][0] = min(dp[i - 1][1] + graph[i][0], dp[i - 1][2] + graph[i][0])
    dp[i][1] = min(dp[i - 1][0] + graph[i][1], dp[i - 1][2] + graph[i][1])
    dp[i][2] = min(dp[i - 1][0] + graph[i][2], dp[i - 1][1] + graph[i][2])

print(min(dp[n - 1]))

첫 번째 집은 입력값 그대로 dp[0]에 넣어주고 두 번째 집부터는 빨간색, 초록색, 파란색으로 칠하는 경우를 모두 계산하는데 그 이전 집의 값 중 같은 색으로 칠하는 경우를 제외한 최솟값을 더해주는 방법으로 갱신해나간다.

 

dp[i][0]은 빨간색으로 칠하는 경우, dp[i][1]은 초록색으로 칠하는 경우, dp[i][2]은 파란색으로 칠하는 경우의 최솟값을 저장하게 되고 결국 마지막 집의 3가지 경우 중 최솟값을 출력하면 된다.

 

느낀 점

다이나믹 프로그래밍 문제를 이제 꽤 풀어봤음에도 모든 경우를 전부 계산하는 아이디어를 떠올리는 것이 쉽지 않았다.