백준_python 1149번 RGB거리 (DP)

<문제 링크>

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

 

 

 

<정답 코드>

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
 
dp = [[0]*3 for _ in range(n)]
dp[0] = arr[0]
 
for i in range(1, n):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2]
 
print(min(dp[n-1]))

문제 자체가 복잡하진 않지만 dp에 익숙하지 않아 풀이 접근이 어려웠다.

코드 원리를 이해하기 쉽개 아래 그림으로 정리했다.