[🥈1 / 백준 1149 / 파이썬] RGB거리 (최적 부분구조)

 

1149번: RGB거리

 

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

예제 입력 3 26 40 83 49 60 57 13 89 99

예제 출력 96

 

 

풀이

 

 

인접한 집의 색이 겹치지 않도록 모든 집을 최소비용으로 칠하는 문제이다.

익숙한 DFS로 먼저 코드를 짜보았다.

 

import sys
n = int(sys.stdin.readline())
house = [list(map(int,sys.stdin.readline().split())) for i in range(n)]

cost = 0
minCost = 1000000

def dfs(num,rgb):
    global cost,minCost
    
    if num == n:
        if minCost > cost:
            minCost = cost
        return
    
    for i in range(3):
        if i == rgb and cost!=0:
            continue
        cost+=house[num][i]
        dfs(num+1,i)
        cost-=house[num][i]
        
dfs(0,0)
    
print(minCost)

 

답은 알맞게 출력되지만, 역시 시간초과를 피할 수 없었다.

많은 재귀 함수의 반복을 요구해서 그런 것 같다.

 

동적 계획법 문제인 만큼 과연 모든 경우의 수를 확인해 봐야 하는가 부터 생각해 보자.

 

문제에서 최적 부분구조가 있는지 확인한다.

최적 부분구조란 큰 문제의 정답을 작은 문제에서 도출해낼 수 있는 구조인 것을 의미한다.

 

피보나치 수열의 경우 재귀로 f(n)을 구할 때 f(n-1) + f(n-2)를 구해야 한다.

마찬가지로 f(5)를 구하고 싶을 때 f(4)와 f(3)을 구해서 더해야 하는데,

f(4)를 구하기 위해선 f(3) + f(2), f(3)을 구하기 위해선 또 f(2) + f(1) …

 

계속해서 이전의 값을 구해야 하는데, 이미 이전에 구했던 값을 기억해 둔다면 굳이 그럴 필요가 없다.

이전에 문제로 풀었었지만, 재귀가 아닌 최적 부분구조로 피보나치 수열을 구한다면

 

f(0)	f(0)	f(1)	f(2)	f(3)	f(4)
1	1	2	3	5	8

 

이런식으로 값을 저장해두고 새로운 다음 값을 구해야 할 때만 계산을 한다.

그러면 f(5)를 구하고 싶을 때 f(4) + f(3) = 8 + 5 = 13 의 과정만 하면 되므로

굳이 이전의 계산을 반복할 필요가 없어진다.

 

 

이제 돌아와서 현재 문제에서 최적 부분구조를 도출할 수 있는지 살펴보자.

	R	G	B
a집	26	40	83
b집	49	60	57
c집	13	89	99

 

a집부터 시작해서 c집까지 겹치지 않게 칠해야 한다.

 

한 번에 c집까지 최적 경로를 구하지 말고 R,G,B 각각을 마지막으로 칠할 때 최소 비용을 구해보자.

 

우선 a집을 base로 b부터 시작해본다.

b집을 R로 끝낼 때 최적의 비용은 a집에 G,B 를 칠하는 비용 중 더 적은 것을 선택하면 된다.

 

따라서 40 + 49 = 89가 된다.

 

마찬가지로 b집을 G로 끝낼 때는 a 집에 R,B를 칠하는 비용 중 더 적은 26 + 60 = 86,

B로 끝낼 때는 26 + 57 = 83이 된다.

 

이렇게 b집을 마지막으로 RGB로 칠할 때 최소 비용은 [ 89, 86, 83 ] 이 된다.

 

 

이제 c집을 칠한다면 a부터 시작하는 것이 아닌 b에서 시작하면 된다.

문제가 다 풀렸다. 이를 코드로 구현하면 아래와 같다.

 

import sys
n = int(sys.stdin.readline())
house = [list(map(int,sys.stdin.readline().split())) for i in range(n)]

minCost = [house[0][0],house[0][1],house[0][2]]

for i in range(1,n):
    temp = [house[i][0] + min(minCost[1],minCost[2]), 
           house[i][1] + min(minCost[0],minCost[2]), 
           house[i][2] + min(minCost[0],minCost[1])]
    
    minCost = [temp[0],temp[1],temp[2]]

print(min(minCost))