[Python] 1149. RGB거리

 

풀이

DP를 n*3의 2차원 형태로 만들어서 각 행의 RGB 비용을 모두 저장해둔다.

DP[i] = [R비용,G비용,B비용] 이런식으로 갱신할 것이다.

DP의 뼈대를 만들었다면 2중 for문을 통해 DP[i][j]에다가 i행의 특정 색상 비용 + i-1행의 나머지 색상 비용 중 작은 값을 더한 값을 넣는다.

현재 빨간색을 택했다면 이전의 파랑, 초록색 중 작은 값을 선택하고 더해서 넣는 셈

 

코드

import sys
input = sys.stdin.readline
n = int(input())
h = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * 3 for _ in range(n)]

for i in range(n):
    for j in range(3):
        if j == 0:
            dp[i][j] = h[i][j] + min(dp[i-1][1],dp[i-1][2])
        elif j == 1:
            dp[i][j] = h[i][j] + min(dp[i-1][0],dp[i-1][2])
        elif j == 2:
            dp[i][j] = h[i][j] + min(dp[i-1][0],dp[i-1][1])
print(min(dp[n-1]))