백준 / 1149번 / RGB거리 / python 파이썬

 

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

 

 

코드

import sys
input = sys.stdin.readline

n = int(input())
HC = []

for _ in range(n):
    HC.append(list(map(int, input().split())))

for i in range(1, n):
    HC[i][0] = HC[i][0] + min(HC[i - 1][1], HC[i - 1][2])
    HC[i][1] = HC[i][1] + min(HC[i - 1][0], HC[i - 1][2])
    HC[i][2] = HC[i][2] + min(HC[i - 1][0], HC[i - 1][1])

print(min(HC[n-1]))

 

이전 집에서 사용한 색을 제외한 색 중 비용이 더 저렴한 색을 칠하는 문제이다.

다이나믹 프로그래밍 (DP) 문제로 DP 테이블을 이용해 현재 집의 비용에 이전 집의 최소 비용을 더해가며 누적된 비용들 중 최솟값을 찾으면 답을 구할 수 있다.