[백준 BOJ / Python] 17404번 RGB거리 2 DP

문제

1번에서 N번까지 나열되어 있는 집들의 색을 RGB 중 한 가지 색으로 칠할 때, 맨 첫 번째 집과 맨 마지막 집의 색이 겹치지 않으면서 앞뒤로 위치한 이웃집끼리의 색도 겹치지 않게 칠하는데 드는 비용의 최솟값을 구하는 문제이다. 이웃집과 색이 겹치는 경우는 최소비용이 들더라도 불가능하다. 예를 들어 R-G-G 나 R-G-B-R 등으로 칠할 수 없다.

풀이

• 기존 RGB거리 문제와의 차이는 맨 첫 번째 집과 맨 마지막 집의 색깔 관계도 살펴봐야 한다는 점이다.
• 최소비용을 도출하는 점화식은 RGB거리 문제와 동일하다. 
  • dp[i]["빨강"] = min(dp[i-1]["초록"], dp[i-1]["파랑"]) + RGB[i]["빨강"]
  • dp[i]["초록"] = min(dp[i-1]["빨강"], dp[i-1]["파랑"]) + RGB[i]["초록"]
  • dp[i]["파랑"] = min(dp[i-1]["빨강"], dp[i-1]["초록"]) + RGB[i]["파랑"]
• 맨 처음과 마지막이 다르기 위해서는 맨 첫 번째 집의 색을 고정한 뒤에 맨 마지막 집의 색이 해당 색과 다르면서 최소비용인 경우를 고려하면 된다.
• 최소 비용의 경우를 선택해 나가기 때문에 맨 첫 번째 집을 빨간색으로 칠한다면 초록색과 파란색은 선택될 수 없도록 제일 큰 수로 초기화를 하면 된다. 또한 맨 마지막 집이 빨간색을 선택하지 못하도록 제일 큰 수로 만든다.

• 여기서 맨 첫 번째 집의 색은 빨강, 초록, 파랑 세 가지가 될 수 있음으로 총 3번 반복하여 최소비용을 비교한다.

알고리즘

1. rgb 비용을 받아 list로 저장한다.
2. 최소 비용이 담길 변수 ans를 큰 수로 정의한다. 
3. 맨 첫 번째 집이 빨강(0), 초록(1), 파랑(2)이 될 수 있음으로 총 3번 다음의 최소비용을 구하는 과정을 반복한다.
   1. rgb 리스트와 동일한 크기로 dp 리스트를 생성한다. 이때 dp에 1001을 입력하여 첫번째 집의 색(i)을 제일 작은 수로 초기화하기 쉽도록 한다.
   2. 첫번째 집을 i번째 색으로 칠한다.
   3. n-1번 반복하면서 점화식을 계산한다.
   4. 마지막 집의 색이 i번째 색과 겹치지 않도록 최댓값으로 덮어버린 뒤, ans를 최솟값으로 업데이트한다.
4. 세 가지 색을 비교한 뒤, ans를 출력한다.

Python 코드

import sys
input = sys.stdin.readline

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

ans = 1000001

for i in range(3):
    dp = [[1001] * 3 for _ in range(n)] #큰 수(1001)로 초기화
    dp[0][i] = rgb[0][i] # 첫번째 집의 색을 제일 작은 수로 고정 (이외는 1001)
    for j in range(1,n):
        dp[j][0] = min(dp[j - 1][1], dp[j - 1][2]) + rgb[j][0] # 삘간색 0
        dp[j][1] = min(dp[j - 1][0], dp[j - 1][2]) + rgb[j][1] # 초록색 1
        dp[j][2] = min(dp[j - 1][0], dp[j - 1][1]) + rgb[j][2] # 파란색 2
    dp[-1][i] = 1000001 # 첫번째 집과 같은 색이면 큰 수를 입력하여 최소비용이 안되도록 함
    ans = min(ans,min(dp[-1])) # 최소비용

print(ans)

문제 출처

17404번: RGB거리 2