[백준/DP] 1149번: RGB거리 (실버1, python)

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

1149번: RGB거리

아이디어

DP 문제이다. 아래와 같이 각 한 인덱스를 기준으로 최솟값을 구해나가면 쉽게 구할 수 있다.

즉, 아래와 같은 점화식을 추론할 수 있다. 

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + datas[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + datas[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + datas[i][2]

 

전체 코드

n = int(input())
datas = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*3 for _ in range(n)] 

answer = 0
prev = -1

dp[0] = datas[0]

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

print(min(dp[-1]))