[BOJ] 1149 : RGB거리 [다이나믹 프로그래밍](Python)

문제 링크

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

1149번: RGB거리

소스 코드

import sys # 빠른 입력

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

dp = graph[0]
for idx in range(1,n):
    pre_red,pre_green,pre_blue = dp[0],dp[1],dp[2] # dp table에 저장된 값
    red,green,blue = graph[idx][0],graph[idx][1],graph[idx][2] # 현재 행

    dp[0] = red + min(pre_green,pre_blue) # 다른 색상 중 작은 값 더하기
    dp[1] = green + min(pre_red,pre_blue)
    dp[2] = blue + min(pre_red,pre_green)

print(min(dp))

 

해설

• 다이나믹 프로그래밍, DP

전형적인 DP 유형에 해당하는 문제라고 볼 수 있겠네요!

문제 조건에 따르면 집의 수 n은 최대 1,000까지니까 (1000,3) 사이즈의 그래프가 만들어질 수 있습니다.

따라서 이를 완전탐색으로 풀게 되면 대략 2^1000... 가늠도 되지 않는 숫자네요.. 😱

(매 집마다 이전과 다른 색을 고를 수 있는 경우의 수는 2니까 이를 천 번 곱한 것입니다)

 

결국 우리는 각 집의 색을 정할 때 항상 최적의 상태가 될 수 있도록 값을 저장하면서 탐색을 수행해야 합니다.

 

상향식 vs 하향식

둘 중에 정답은 없습니다만 편한 걸 골라서 하시면 될 것 같아요.

저는 앞에서부터 뒤로, 즉 시작부터 마지막까지 값을 하나씩 쌓아 나가는 상향식으로 문제를 풀이했습니다.

맨 처음엔 그래서 dp 테이블에 graph의 첫 행을 저장해줍니다.

dp 테이블의 세 원소는 각각 해당 집에 마지막으로 빨강, 초록, 파랑을 칠하는 최소의 비용을 뜻합니다.

 

문제에서 빨강, 초록, 파랑(R,G,B) 순서로 비용이 주어진다고 했습니다.

그래서 저는 현재 dp 테이블에 저장된 값을 이전 집에서 빨강, 초록, 파랑을 칠했을 때의 최소 비용으로 꺼냈습니다.

graph에서의 세 원소는 이번 집에 빨강, 초록, 파랑을 칠할 때의 최소 비용을 뜻합니다.

 

따라서 dp의 값을 업데이트 할 때는 현재(graph) 집을 칠할 때의 비용 + 이전에 다른 색을 칠한 경우의 최소 비용 으로 저장합니다.

 

첫 번째 예시를 자세히 살펴볼게요.

n = 3
graph = [[26,40,83],
         [49,60,57],
         [13,89,99]]

우선 dp 테이블은 첫 행으로 뽑아냅니다.

dp = [26,40,83]

 

이미 dp 테이블을 그래프의 첫 행에서 뽑아냈으므로 반복문의 범위는 1부터 시작됩니다.

따라서 반복문의 첫 번째 작업은 '첫 행으로 뽑아낸 dp의 값'과 '첫 인덱스로 뽑아낸 graph의 값'을 비교하는 것입니다.

# 이전 집에 칠해진 색에 따른 비용
dp = [26,40,83]
pre_red,pre_green,pre_blue = 26,40,83
# 현재 집에 칠해질 색에 따른 비용
graph[1] = [49,60,57]
red,green,blue = 49,60,57

그러므로  이 둘을 조합한 값을 dp 테이블에 업데이트 해줘야 하는데,

이때 현재 집에 칠할 색과 다른 두 개의 색 중에 더 적은 비용이 들었던 것을 저장해줍니다.

# dp[R],dp[G],dp[B]
dp[0] = 49 + min(40,83) # 89
dp[1] = 60 + min(26,83) # 86
dp[2] = 57 + min(26,40) # 83

 

이 과정을 마지막 집까지에 대해서도 똑같이 반복해줍니다.

결과적으로 dp에는 마지막 집에 각각 빨강, 초록, 파랑을 칠했을 때의 최소 비용이 저장되어 있습니다.

이제 이 중에서 가장 작은 값을 출력하면 정답이 됩니다.