[백준 - Python] 1149. RGB거리 (DP)

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

1149번: RGB거리

 

코드

n = int(input())
a = [0] * n

for i in range(n):
    a[i] = list(map(int, input().split()))

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

print(min(a[n-1][0], a[n-1][1], a[n-1][2]))

 

N개의 집을 세가지 색으로 칠하는데,

이웃한 집들의 색을 같게 칠하면 안된다는 조건이 있다.

 

각 집들을 세 가지 색으로 칠할 때 드는 비용이 입력으로 들어올 때,

조건을 만족하며 모든 집을 칠하는 비용의 최솟값을 구하는 문제였다.

 

각 집마다 각 색으로 칠할 때 드는 비용을 저장하고

최종 집을 칠한 후에 드는 최소 비용을 구해서 출력한다.

 

따로 DP 리스트를 생성하지 않고

각 집들을 칠할 때 드는 비용을 저장한 변수에

현재 순회하고 있는 집까지 칠하는데 드는 비용을 저장함으로써

메모리 효율적인 코드라 볼 수 있다.

 

일반적인 경우와 다르게 DP 리스트가 이차원 배열이라는 점에서

기억해두면 좋을 문제인 것 같다.