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

문제

1번에서 N번까지 직선으로 나열되어 있는 집들의 색을 앞뒤로 위치한 이웃집과 겹치지 않게 RGB 중 한 가지 색으로 칠할 때 드는 비용의 최솟값을 구하는 문제이다.

이웃집과 색이 겹치는 경우는 최소비용이 들더라도 불가능하다. 예를 들어 R-R-G 나 R-G-B-B 등으로 칠할 수 없다.

풀이

• 서로 겹치지 않게 색칠하려면, 현재 위치(i)에서 초록색을 선택했을 경우 이전 위치(i-1)에는 빨간색이나 파란색을 선택해야 한다.
• i번째 집을 초록색으로 칠한다면 i까지의 최소 비용은 i-1번째 집이 빨간색과 파란색일 경우 중 더 작은 비용을 가진 색의 비용과 i번째 집의 초록색 비용을 더한 값이 된다.

• 모든 위치에서 앞집과 다른 색으로 최소비용을 계산해줌으로써 색이 겹치지 않게 집을 칠하는 비용의 최솟값을 도출할 수 있다.

• 이를 점화식으로 표현하면 다음과 같다.
  • 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]["파랑"]

알고리즘

1. dp 리스트를 t 길이로 생성한다.
2. 0번째 값은 이전 집이 없음으로 rgb 리스트와 동일하다.
3. n-1번 반복하면서 점화식을 계산한다.
4. 마지막 집에서 색의 비용을 비교하여 최소비용을 출력한다.

Python 코드

import sys
input = sys.stdin.readline
n = int(input())
rgb = [list(map(int, input().rstrip().split())) for _ in range(n)]
dp = [[0] * 3 for _ in range(n)] # 0으로 초기화
dp[0] = rgb[0]
for i in range(1, n):
    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + rgb[i][0] # 삘간색 0
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + rgb[i][1] # 초록색 1
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + rgb[i][2] # 파란색 2
print(min(dp[-1]))

문제 출처

1149번: RGB거리