1149 - RGB거리 / silver 1 / DP

+"""
1149 - RGB거리 / silver 1 / DP
"""
import sys

input = sys.stdin.readline

house = []
N = int(input().rstrip())
for _ in range(N):
    house.append(list(map(int, input().split())))
for i in range(1, len(house)):
    house[i][0] = min(house[i - 1][1], house[i - 1][2]) + house[i][0]
    house[i][1] = min(house[i - 1][0], house[i - 1][2]) + house[i][1]
    house[i][2] = min(house[i - 1][0], house[i - 1][1]) + house[i][2]

print(min(house[N - 1][0], house[N - 1][1], house[N - 1][2]))

1. 입력 받은 것을  house 리스트에 넣기

EX) house = [[26, 40, 83], [49, 60, 57], [13, 89, 99]]

 

2. DP 알고리즘

house[1][0] 을 선택 했을 시, 최소 비용은 (house[0][1], house[0][2] 둘 중 최소 값) + house[1][0] 이다.

즉, min(40, 83) + 49 를 house[1][0] 에 최신화 시키기

똑같은 로직으로 house[1][1], house[1][2] 최신화 시키기

이러한 반복을 house 마지막 인덱스까지 반복