[DP] 백준 #1149 RGB 거리 - Python

🗂️ 문제

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

 

💡 접근법

모든 집에 대해 비용을 적은 것부터 많은 것으로 정렬한 뒤, 비용이 적은 집에 대해서 우선적으로 처리하는 방식이다.

즉, 현재 순간에서 가장 비용이 적은 것을 선택한다.

 

이때 문제에서 제시한 바와 같이, 이전 집과는 같은 색을 칠하지 않는 조건을 처리한다.

 

😎 내 코드

import sys
from collections import deque

N = int(sys.stdin.readline())

house_cost = []
RGB = ["R", "G", "B"]
for i in range(N):
    costs = list(map(int, sys.stdin.readline().split()))
    for c, r in zip(costs, RGB):
        house_cost.append((i+1, c, r))  # (집 번호, 비용, 색상)

house_cost.sort(key=lambda x: x[1])
house_cost = deque(house_cost)

complete_house = [()] * (N+1)

cost = house_cost.popleft()
complete_house[cost[0]] = cost

while house_cost:
    cost = house_cost.popleft()
    house_num = cost[0]
    used_color = []

    if complete_house[house_num] == ():  # 아직 칠하지 않은 집
        if house_num == 1:  # 1번 집인 경우
            if complete_house[2] != ():  # 2번째 집이 칠해진 경우 used_color 리스트에 추가
                used_color.append(complete_house[2][2])
        elif house_num == N:  # N번 집인 경우
            if complete_house[N-1] != ():  # N-1번째 집이 칠해진 경우 used_color 리스트에 추가
                used_color.append(complete_house[N-1][2])
        else:  # i(2 ≤ i ≤ N-1)번 집인 경우
            if complete_house[house_num-1] != ():  # i-1번 집이 칠해진 경우
                used_color.append(complete_house[house_num-1][2])
            if complete_house[house_num+1] != ():  # i+1번 집이 칠해진 경우
                used_color.append(complete_house[house_num+1][2])
    
        if cost[2] not in used_color:
            complete_house[cost[0]] = cost

total = 0
for i in range(1, N+1):
    total += complete_house[i][1]
print(total)

하지만 그리디(즉, 비용이 작은 것을 우선 선택하는 방식)는 현재 순간의 선택만을 최적화한다.

이 문제에서는 이후 선택이 앞선 선택에 의해 영향을 받기 때문에, 전체적으로는 최적의 해를 보장하지 못한다.

 

따라서 DP로 해결해야 한다.

 

👀 배운 코드

import sys

N = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [[0] * 3 for _ in range(N)]
dp[0] = arr[0]

for i in range(1, N):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2]

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

먼저, DP 조건에 맞는지 확인해 보면,

 

1) 큰 문제를 작은 문제로 쪼갤 수 있는가?

그렇다. N행까지 모두 더한 최소 비용은 N-1행까지의 최소 비용 문제로 쪼개진다.

2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일한가?

그렇다. 이전 집까지 최소 비용 결과에 현재 집의 값을 더해서 최소 비용을 업데이트하게 되므로 이전의 결과를 그대로 가져와서 사용한다고 볼 수 있다.

 

즉, 집에 색을 하나씩 칠하면서 누적된 최소 비용값을 dp 테이블에 저장하고, 마지막 집까지 도달했을 때 가장 작은 비용 값을 출력하면 된다. 이 규칙을 점화식으로 나타내면 **dp[i][0] = min(dp[i-1][1], dp[i-1][2])**이다.

 

🧐 배운 점

항상 dp 규칙을 찾아내는 게 어려운 것 같은데… 시간 복잡도를 계산해 보면서 어느 알고리즘일지 유추하고, DP 조건에 맞는지 확인해보는 습관을 들여야겠다.

 

✅ 정답 확인