백준 1149 RGB거리

과정

• 다이나믹 프로그래밍
  • 문제를 수행하며 중간 값을 계속 업데이트하며 풀어나가는 방식
• 앞 줄과 색이 겹치지만 않도록 색을 칠하기
  • 각 집의 숫자를 (위 줄에서 가능한 최소값 + 집의 숫자) 로 업데이트
  • 위 줄에서 발생하는 최소 값만을 반영하여 값을 계속 업데이트 한다.

import sys
input = sys.stdin.readline
N = int(input())
map_lst = [list(map(int, input().split())) for _ in range(N)]
for i in range(1, N):
    map_lst[i][0] += min(map_lst[i-1][1], map_lst[i-1][2])
    map_lst[i][1] += min(map_lst[i-1][0], map_lst[i-1][2])
    map_lst[i][2] += min(map_lst[i-1][0], map_lst[i-1][1])

print(min(map_lst[-1]))

동적 계획법은 계속 풀어봐야 할 것 같다.
점화식을 먼저 세우는 것을 연습해야겠다.