BOJ 1149번: RGB거리

www.acmicpc.net/problem/1149

1149번: RGB거리

문제풀이:

dp를 어떻게 짜야 할 지 생각해내는 것이 어려웠다.

최솟값을 더하는 방법으로 하자니 동일한 비용이 나오는 경우를 고려하는 것이 어려웠고..

그래서 각각의 경우를 모두 구하는 것이구나 하는 걸 깨달았다..(사실 힌트를 좀 받았다..)

그걸 깨닫고 나니 푸는 것은 간단했다.

 

import sys

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

dp = [[0,0,0] for _ in range(N)]
dp[0] = cost[0]
for i in range(1,N):
    dp[i][0] = min(dp[i-1][1]+cost[i][0], dp[i-1][2]+cost[i][0])
    dp[i][1] = min(dp[i-1][0]+cost[i][1], dp[i-1][2]+cost[i][1])
    dp[i][2] = min(dp[i-1][0]+cost[i][2], dp[i-1][1]+cost[i][2])
print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2]))