[Python][DP] 백준 Q1149: RGB 거리

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

 

문제의 핵심은,

i번째 집의 색은 인접한 집의 색과 달라야 한다는 점이다.

즉, 내가 이번에 초록색으로 칠했다면 그 다음 집은 반드시 (빨강, 파랑)색 중 하나여야만 한다.

 

이 점을 활용해서 DP로 코드를 짜보자.

---

 

1. 입력 : n(전체 집의 개수), arr(각 집별 빨초파 가격 리스트)

import sys

n = int(sys.stdin.readline())
arr = []
for _ in range(n) :
    a = list(map(int, sys.stdin.readline().split()))
    arr.append(a)

 

2. [DP] 계산 : 모든 가능한 계산 값 리스트에 저장, 업데이트

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

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

arr[i]는 [빨, 초, 파]로 구성되는데,

• arr[i][0]을 i번째 집을 빨강으로 칠했을 때의 전체 합 최소 비용,
• arr[i][1]을 i번째 집을 초록으로 칠했을 때의 전체 합 최소 비용,
• arr[i][2]을 i번째 집을 파랑으로 칠햇을 때의 전체 합 최소비용

으로 업데이트 해주는 코드이다.

 

 

 

만약 내가 2번째 집에서 빨강을 칠한다고 했을 때,

이때의 전체 최소 비용은 이전 집의 (초, 파) 중 최솟값을 선택해 더하는 것이다.

+ 마찬가지 초록은 이전 집의 (빨, 파) 중 최솟값, 파랑은 이전 집의 (빨, 초) 중 최솟값을 더하면 된다.

 

이 과정을 끝까지 반복하면,

결국 arr[n-1]에는, 마지막 집에서 각 색깔을 선택했을 때 발생하는 최솟값들이 배열에 저장된다.

 

따라서 마지막 배열 arr[n-1] 의 최솟값이, 집을 칠하는 최소 비용이 된다.

---

전체 코드

import sys

n = int(sys.stdin.readline())
arr = []
for _ in range(n) :
    a = list(map(int, sys.stdin.readline().split()))
    arr.append(a)

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

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