DP 문제풀이 #2 - RGB 거리

첫 번째 문제에 이어서 선택한 문제는 백준 온라인 저지의 1149번 문제가 되겠다. 이웃과 서로 다른 색깔의 페인트로 집을 칠할 때, 가능한 초소의 비용을 찾는 문제다. 색은 R, G, B로 한정되어 있으며, 집의 수는 사용자의 입력으로 결정된다. 예를 들면, 아래와 같은 경우를 생각해볼 수 있다. 

            R      G      B

집1|    26    40    83

집2|    49    60    57

집3|    13    89    99

이 경우의 최소의 값은 (집1-R, 집2-B, 집3-R)로 색칠하는 방법으로 최소비용 96이 답안이 된다. 그리디 알고리즘이나 다른 방법을 통해서도 문제를 풀 수 있겠지만, Overlapping SubProblem 구조와 Optimal Substructure 특징이 두드러지는 문제이므로 다이나믹 프로그래밍을 활용하면 쉽게 해결할 수 있다. 

그럼 이제부터 다이나믹 프로그래밍을 적용하여 문제를 풀어보자. 먼저 이전 문제와 동일한 방식으로 메모이제이션을 위해서 색상에 따른 가격을 정보를 저장할 이차원 리스트(prices)와 현재까지 계산된 소문제의 최소값을 저장을 위한 이차원 리스트(dp)를 선언하자. 그리고 각 행이 집을 의미하고 있으므로 dp의 첫 번째 행을 prices의 첫 번째 행으로 초기화시켜주자.

두 번째 집부터는 아래와 같이 반복되는 형태의 연산 과정을 생각할 수 있다. 이전 집의 색상을 고려해서 현재 집이 선택가능한 색상들 중에 최소 비용이 책정되는 색상을 선택하는 것이다. 예를 들어, 위 경우에서 (집2-R)을 계산하기 위해서는 (집1-R)을 제외한 (집1-G), (집1-B) 중에서 최소값을 합산해서 계산한다.

앞선 숫자삼각형 문제 풀이 때와 동일하게 반복되는 계산 패턴을 찾았다면, 이를 점화식으로 일반화하는 과정이 필요하다. 위의 계산 과정을 아래와 같이 표현할 수 있다. 아래의 식은 이번 집까지의 최소값은 곧, 이전 집의 색상을 고려한 최소값과 합산하여 계산함을 의미한다.

위에서 메모이제이션 기법을 위해서 미리 선언했던 리스트와 반복되는 계산 패턴을 통해서 정의된 점화식을 아래의 코드에서 확인해볼 수 있다.

import sys if __name__ == '__main__': n = int(sys.stdin.readline()) # 배열처럼, 미리 2차원 공간을 할당해놓는다. prices = [[0 for col in range(n)] for row in range(n)] dp = [[0 for col in range(3)] for row in range(n)] # 사용자 입력을 받아서 각 집 별로 색칠하는 비용을 저장 # str -> int 캐스팅 i = 0 while i < n: price = input().split() price = [int(i) for i in price] prices[i] = price i += 1 # dp[0]을 초기화 dp[0] = prices[0] # dp[1]부터 dp[n]까지 계산 j = 1 while j < n: dp[j][0] = min(dp[j - 1][1] + prices[j][0], dp[j - 1][2] + prices[j][0]) dp[j][1] = min(dp[j - 1][0] + prices[j][1], dp[j - 1][2] + prices[j][1]) dp[j][2] = min(dp[j - 1][0] + prices[j][2], dp[j - 1][1] + prices[j][2]) j += 1 print(min(dp[n-1]))