[알고리즘] 동적 계획법(Dynamic Programming) - 백준 1149번 RGB거리

import sys
n = int(sys.stdin.readline().rstrip())
house = []

# 빨강, 초록, 파랑 배열 만들기
for _ in range(n):
    color = list(map(int, sys.stdin.readline().rstrip().split(' ')))
    house.append(color)

# 동적 계획법으로 이웃하는 색과 다른 색 더하기
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 배열 안에 입력 받은 빨강, 초록, 파랑색 비용을 넣는다.
2. 동적 계획법을 이용하여, 배열의 앞에서부터 값을 더해나간다.
3. house의 마지막 배열 요소 중 최소 값을 찾는다.