[Python] 백준 1149 RGP거리 문제풀이 및 정답코드

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보다 작거나 같은 자연수이다.

출력

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

 

문제해설

이번 문제는 간단하다.

인접한 집과는 반드시 다른 색으로 색칠되어야 한다.

우리는 모든 집을 최소의 비용으로 칠해야 하며,

그 때의 비용을 출력해야 된다.

 

첫 집이 R색으로 칠해졌으면, 다음 집은 반드시 B와 G 중에 하나로 칠해야 한다.

 

두 경우에서도 B로 칠하면 R과 G

G로 칠하면 R과 B로 칠해야 한다.

 

색칠하는 경우의 수

 

위 그림처럼 첫 집을 R색으로 고정하고 경우를 살펴보자.

그림을 보면 본 문제를 작은 문제로 쪼갤 수 있다.

같은 색으로 칠하게 되는 경우가 반복되는 것을 알 수 있다.

 

위 그림처럼 세 번째 집을 빨간색으로 칠할 때의 비용이 두 번 반복되어 계산된다.

따라서 본 문제는 DP(다이나믹 프로그래밍)으로 해결할 수 있다.

 

각 집을 특정 색을 칠할 때의 최소 비용을 계산하면 다음 번에 다시 동일 색을 칠할 때, 따로 계산하기 않아도 된다.

위 그림의 예시는 적은 수지만, 집의 개수가 많아지면 분명히 시간초과가 발생할 것이다.

 

또한 본 문제는 아래부터 차근차근 계산하는 Bottom-Up 방식으로 해결하기 쉬운 문제이다.

따라서 제일 마지막 집의 색칠 비용을 저장해두고,

매번 계산할 때까지 최소 비용을 골라서 저장해주면 된다.

 

따라서 본인은, 각 집을 R, G, B 각각으로 칠했을 때의 모든 경우 중, 가장 비용이 적은 경우를 DP 배열에 저장했다.

 

그리고 매 순간 계산하고 이를 기록하는 Memoization을 통해 최소 비용을 계산했다.

 

코드를 보면 쉽게 이해할 수 있다.

정답코드

def memo(cur, color):
    # print(color, cur, len(dp), len(dp[0]))
    if dp[color][cur] != -1:
        return dp[color][cur]
    
    if color == 0: # R
        target_color = (1, 2)
    elif color == 1: # G
        target_color = (0, 2)
    else: # B
        target_color = (0, 1)
    
    if cur+1 < len(dp[0]):
        dp[color][cur] = min(memo(cur+1, target_color[0])+total_price[cur][color], memo(cur+1, target_color[1])+total_price[cur][color])
    
    return dp[color][cur]


n = int(input())

total_price = []
dp = [[-1 for _ in range(n)] for _ in range(3)]

for i in range(n):
    total_price.append(list(map(int, input().split())))

for i in range(3):
    dp[i][-1] = total_price[-1][i]
    
print(min([memo(0, 0), memo(0, 1), memo(0, 2)]))