1149번 - RGB거리

풀이

dp를 이용해 각 위치까지의 최솟값을 저장해서 문제를 해결했다.

 

dp[home][color]은 home 번째 집의 color 색을 사용했을 때 home 번째까지 사용한 비용의 최솟값이다.

따라서, dp[0]의 값들은 각각 cost[0]의 값들로 초기화했다.

또한, 반복문을 통해 각 집들의 dp값을 구했다.

(빨강으로 칠했을 때의 dp값은 이전 집의 파란색의 dp값과 초록색의 dp값 중 작은 값과 더해주면 된다.)

 

코드

import sys


input = sys.stdin.readline
N = int(input())
cost = [list(map(int, input().split())) for _ in range(N)]
dp = [[cost[0][0], cost[0][1], cost[0][2]] for _ in range(N)]

for home in range(1, N):
    for color in range(3):
        dp[home][color] = cost[home][color] + min(dp[home-1][(color+1) % 3], dp[home-1][(color+2) % 3])

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