(BOJ)-1149, Python

문제 요약

출처: (BOJ)1149 - RGB거리

집의 수($N$)과 각 집에 칠할 수 있는 Red, Green, Blue 색상의 비용이 주어진다. 모든 집을 칠할 때, 아래 조건을 만족하면서 모든 집을 칠하는데 드는 최소 비용을 구하는 문제이다.

• $i$번 째 집은 $i-1, i+1$의 집과 다른 색을 칠해야 한다.($2\le i \le N-1$)

접근 과정

1. 완전탐색 접근(재귀)

RGB 중 하나를 선택한 경우, 총 세 개의 경우로 나누기 위해 재귀를 활용하여 접근하기로 했다. 결과는 시간초과였다.

코드 구현

N = int(input())
RGB = [list(map(int, input().split())) for _ in range(N)]
min_value = 1e9

def recursion(idx, color, value):
    global min_value
        
    if idx == N:
        min_value = min(min_value, value)
        return       
    if color == 0: #전 컬러가 RED(0)이라면
        recursion(idx+1, 1, value + RGB[idx][1])
        recursion(idx+1, 2, value + RGB[idx][2])
    elif color == 1: #전 컬러가 GREEN(1)이라면
        recursion(idx+1, 0, value + RGB[idx][0])
        recursion(idx+1, 2, value + RGB[idx][2])
    else: #전 컬러가 BLUE(2)이라면
        recursion(idx+1, 0, value + RGB[idx][0])
        recursion(idx+1, 1, value + RGB[idx][1])
    
recursion(0, 0, 0)
recursion(0, 1, 0)
recursion(0, 2, 0)

print(min_value)

2. DP 접근(메모이제이션)

바로 재귀 코드를 바탕으로 DP(메모이제이션) 로 접근하였고, 결과는 맞았습니다!

코드 구현

import sys
sys.setrecursionlimit(40000) #파이썬 재귀 한도로 런타임 에러 발생 후 추가함

N = int(input())
RGB = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1 for _ in range(3)] for _ in range(N)]

def recursion(idx, rgb):
        
    if idx == N:
        return 0
    if dp[idx][rgb] != -1:
        return dp[idx][rgb]
    
    if rgb == 0:
        dp[idx][rgb] = min(recursion(idx+1, 1) + RGB[idx][1], recursion(idx+1, 2) + RGB[idx][2])
    if rgb == 1:
        dp[idx][rgb] = min(recursion(idx+1, 0) + RGB[idx][0], recursion(idx+1, 2) + RGB[idx][2])
    if rgb == 2:
        dp[idx][rgb] = min(recursion(idx+1, 0) + RGB[idx][0], recursion(idx+1, 1) + RGB[idx][1])
    
    return dp[idx][rgb]

for i in range(3):
    recursion(0,i)

print(min(dp[0]))

3. DP 접근(점화식)

위에서 문제를 Top-Down으로 접근했다면, 이번에는 Bottom-Up으로 접근해보았다. 복잡한 규칙을 생각하지도 않아도 되고, 현재 집에서 선택한 색상과 다른 색상 중 최소 비용을 선택하며 결과를 업데이트하며 나아가면 된다. 이를 바탕으로 점화식을 다음과 같이 세울 수 있다.

• R을 선택했다면,
  • $dp[idx+1][r] = min(dp[idx][g], dp[idx][b]) + cost[idx][r]$
• G를 선택했다면,
  • $dp[idx+1][g] = min(dp[idx][r], dp[idx][b]) + cost[idx][g]$
• B를 선택했다면,
  • $dp[idx+1][b] = min(dp[idx][r], dp[idx][g]) + cost[idx][b]$

코드 구현

N = int(input())
RGB = [list(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(3)] for _ in range(N+1)]

for idx in range(N):
    for rgb in range(3):
        if rgb == 0: #RED
            dp[idx+1][rgb] = min(dp[idx][1], dp[idx][2]) + RGB[idx][rgb]
        if rgb == 1: #GREEN
            dp[idx+1][rgb] = min(dp[idx][0], dp[idx][2]) + RGB[idx][rgb]
        if rgb == 2: #BLUE
            dp[idx+1][rgb] = min(dp[idx][0], dp[idx][1]) + RGB[idx][rgb]

print(min(dp[N]))

회고

어려운 규칙을 알아내야만 풀 수 있는 문제가 아니지만, Bottom-Up 접근을 연습해보기에 좋은 문제라고 생각한다. 코드가 더 간결하게 나오는 것 같다. 아직까지는 경우의 수를 쪼개는 문제에서는 Top-down 접근이 아무래도 조금 더 직관적이고 구현하기 수월한 것 같다.