[백준] 1149번 : RGB거리

안녕하세요. 매일공부하는 개발자 빅광스입니다.

오늘은 다이나믹 프로그래밍 문제를 풀어보겠습니다.

 

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

1149번: RGB거리

먼저 저는 다이나믹 사고 능력이 아직 부족하여 모든 경우의 수를 다 따져보는 계산을 해보았습니다.

dfs 탐색을 통하여 모든 경우를 다 방문하고 방문한 값을 저장하고 그 저장한 값들중 min 값을 구하여 정답을 도출하였습니다.

 

char = ['R', 'G', 'B']
r = []
g = []
b = []

N = int(input())
for i in range(N):
    i, j, k = map(int, input().split())
    r.append(i)
    g.append(j)
    b.append(k)
    
total = 0
result = []
queue = []

def colorhouse(i, char):

    if(N > i >= 0):
        if char == 'R':
            queue.append(r[i])
        elif char == 'G':
            queue.append(g[i])
        else:
            queue.append(b[i])
        
    if len(queue) == N:
        return result.append(sum(queue))

    if(len(result) and min(result) < sum(queue)):    
        return
    
    if char == 'R': # R일때
        colorhouse(i+1,'G')
        queue.pop()
        colorhouse(i+1,'B')
        queue.pop()
        
    elif char == 'G': # G일때
        colorhouse(i+1, 'R')
        queue.pop()
        colorhouse(i+1, 'B')
        queue.pop()
        
    else: # B일때
        colorhouse(i+1, 'R')
        queue.pop()
        colorhouse(i+1, 'G')
        queue.pop()
        
colorhouse(0, "R")
queue = []
colorhouse(0, "G")
queue = []
colorhouse(0, "B")
print(min(result))

이렇게 한다면 시간 복잡도는 n개의 집이 주어졌을때 2^n 이라는 엄청나게 큰 시간복잡도를 가지게 됩니다.

따라서dfs탐색으로 백트래킹을 하더라도 원하는 시간복잡도에 도달하기 힘들 것 입니다.

 

다이나믹 프로그래밍 방식으로 문제를 접근하기위하여 Sub Problem으로 문제를 접근해야합니다.

현재 색칠한 가치의 총합은 현재 이전에 구했던 가치와  현재 뽑을 색상의 가치를 더하여 가장 최소 값을 구하면 됩니다.

1) R일때 -> 이전에 선택한 집은 G or B가 선택된다.

2) G일때 -> 이전에 선택한 집은 R or B가 선택된다.

3) B일때 -> 이전에 선택한 집은 R or G가 선택된다.

이 세개의 조건중에 가장 작은 값을 선택하면 현재 색칠한 가치를 구할 수 있습니다.

이런 조건으로 우리는 현재 가치를 이전에있는 가치중 현재 집과 더하여 작은 값을 선택하기때문에 우리는 이전에 있는 값 을 알아야 합니다.

 

위의 조건을 코드로 나타내면 다음과 같습니다.

n=int(input())
dp=[list(map(int,input().split())) for _ in range(n)]
ans=[[0]*3 for _ in range(n+1)]
for i in range(1,n+1):
    ans[i][0] = min(ans[i-1][1],ans[i-1][2])+dp[i-1][0]
    ans[i][1] = min(ans[i-1][0],ans[i-1][2])+dp[i-1][1]
    ans[i][2] = min(ans[i-1][0],ans[i-1][1])+dp[i-1][2]
print(min(ans[n][0],ans[n][1],ans[n][2]))

우리는 ans[n][0]의 값을 구하기위하여 a[1][0] ... a[n-1][0]을 구해야 합니다.

이전에 있는 값들 (Sub Problem)으로 현재의 Main Problem을 구 할 수 있습니다.