[백준] 1149번 RGB거리 - 파이썬/DP

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

N = int(input())
H_list = []
for i in range(N):
    H_list.append(list(map(int, input().split())))

=for i in range(1, N):
    H_list[i][0] = min(H_list[i - 1][1], H_list[i - 1][2]) + H_list[i][0]
    H_list[i][1] = min(H_list[i - 1][0], H_list[i - 1][2]) + H_list[i][1]
    H_list[i][2] = min(H_list[i - 1][0], H_list[i - 1][1]) + H_list[i][2]
print(min(H_list[N - 1][0], H_list[N - 1][1], H_list[N - 1][2]))

예시로 아래와 같이 주어졌다.

3
26 40 83
49 60 57
13 89 99

이 그래프를 DP처럼 사용한다.

만약 두번째 집에서 초록색을 사용한다고하면 첫번째 집에서 빨간색이나 파란색을 사용했을 것이다.

빨+초 = > 26+60 = 86
파+초 = > 83+60 = 143

86이 더 작으므로 86으로 바꿔준다.

이런식으로 DP를 적용하면

26 40 83           26 40 83
49 60 57     ->    89 86 83
13 89 99           96 172 185

가 되고 마지막 줄의 최소값을 구해주면 된다.