백준 1149 RGB거리 (Python)

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

1149번: RGB거리

이번주도 DP가 주제이다.

 

DP = 단계별로 값을 저장이기 때문에 문제를 보자마자

한 줄마다 각 단계를 어떻게 저장할 수 있을지를 먼저 생각해보았다.

 

일단 각 줄마다 영향을 받는 것은 해당 줄의 전 줄이다.

만약 3번째 줄을 본다면, 2번째 줄의 집에만 영향을 받고 1번째 줄의 집에 색에는 영향을 받지 않는다.

 

그럼 한 줄씩 진행해가며, 전 단계의 집을 살핀 후 각 색마다 만들 수 있는 최소 비용을 구한다.

그렇게 한 단계씩 DP를 진행해가며, 마지막에는 그 중에서 최소값을 구해 출력하게 된다.

import sys

N = int(sys.stdin.readline())

min_list = [0 for i in range(3)]

for i in range(N):
    color = list(map(int, sys.stdin.readline().split()))
    min_list = [
        min(min_list[1], min_list[2]) + color[0],
        min(min_list[0], min_list[2]) + color[1],
        min(min_list[0], min_list[1]) + color[2]
    ]

print(min(min_list))