[백준] 1149 - RGB거리 [Python(파이썬)]

문제

www.acmicpc.net/problem/1149

1149번: RGB거리

 

풀이

이 문제의 핵심은 같은 색으로 연속해서 집을 색칠할 수 없다는 것이다.

다시 말해서 같은 색이 아닌 색으로 다음 집을 칠해야 한다는 것이다. 이것이 점화식을 세우는 핵심이다.

이것을 간단하게 표현하면 다음과 같다.

 

이전 집의 색깔	현재 집의 색깔
G or B	R
R or B	G
R or G	B

그림으로 표현

 

이를 통해 점화식으로 표현하면 다음과 같다.

R, G, B = 0, 1, 2

dp[i][R] = min(dp[i-1][G], dp[i-1][B]) + arr[i][R]
dp[i][G] = min(dp[i-1][R], dp[i-1][B]) + arr[i][G]
dp[i][B] = min(dp[i-1][R], dp[i-1][G]) + arr[i][B]

 

예시를 통해 구체적으로 살펴보자.

다음과 같은 입력이 주어졌을 때, 모든 집을 칠하는 비용의 최솟값은 60이다.

비용(arr)	0	1	2
R	10	40	80
G	20	20	10
B	30	40	100

 

1) DP 테이블의 초기상태 (i = 0)

DP	0	1	2
R	10	0	0
G	20	0	0
B	30	0	0

2) i = 1

DP	0	1	2
R	10	min(20, 30) + 40 = 60	0
G	20	min(10, 30) + 20 = 30	0
B	30	min(10, 20) + 40 = 50	0

3) i = 2

DP	0	1	2
R	10	60	min(30, 50) + 80 = 110
G	20	30	min(60, 50) + 10 = 60
B	30	50	min(60, 30) + 100 = 130

 

코드

import sys

N = int(input())
arr = []
R, G, B = 0, 1, 2

for _ in range(N):
    costs = [int(x) for x in sys.stdin.readline().split()]
    arr.append(costs)

dp = [[0]*3 for _ in range(N)]
dp[0][R], dp[0][G], dp[0][B] = arr[0][R], arr[0][G], arr[0][B]

for i in range(1, N):
    dp[i][R] = min(dp[i-1][G], dp[i-1][B]) + arr[i][R]
    dp[i][G] = min(dp[i-1][R], dp[i-1][B]) + arr[i][G]
    dp[i][B] = min(dp[i-1][R], dp[i-1][G]) + arr[i][B]

print(min(dp[N-1]))