[BOJ][Python] 1149 RGB거리

Overview

• 체감 난이도: ★★★☆☆
• 문제 레벨: 실버 1
• 문제 유형: DP
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

https://www.acmicpc.net/problem/1149

 

[문제 풀이]

조건: 각 집은 빨강, 초록, 파랑으로 색을 칠할 수 있다. 단, 인접한 집끼리는 같은 색으로 칠할 수 없다.

아이디어: 이전 집에서 선택한 색에 따라 현재 집에서 선택할 수 있는 색의 비용을 최소화한다. 

 

예제 입력 1 로 동작 과정을 살펴보자. 

집 번호	빨강(R)	초록(G)	파랑(B)
1	26	40	83
2	49	60	57
3	13	89	99

 

* DP 테이블 구성

• dp[i][0] : i 번 집을 빨강으로 칠할 때 최소 비용 
• dp[i][1] : i 번 집을 초록으로 칠할 때 최소 비용
• dp[i][2] : i 번 집을 파랑으로 칠할 때 최소 비용

* 초기화 (첫 번째 집을 칠하는 비용으로)

dp[0][0] = 26, dp[0][1] = 40, dp[0][2] = 83 

 

* 점화식 (다음 집을 칠할 때는 이전 집에서 칠한 색을 고려해서 최소 비용을 계산한다.)

• dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
  • i 번째 집을 빨강으로 칠하려면, 이전 집을 초록 또는 파랑으로 칠한 경우 중 최소 비용을 더한다. 
• dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
  • i 번째 집을 초록으로 칠하려면, 이전 집을 빨강 또는 파랑으로 칠한 경우 중 최소 비용을 더한다.
• dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])
  
  • i 번째 집을 파랑으로 칠하려면, 이전 집을 빨강 또는 초록으로 칠한 경우 중 최소 비용을 더한다. 

* 계산 과정

집 번호 (i)	빨강 비용 dp[i][0]	초록 비용 dp[i][1]	파랑 비용 dp[i][2]
1	26	40	83
2	49 + min(40, 83) = 89	60 + min(26, 83) = 86	57 + min(26, 40) = 83
3	13 + min(86, 83) = 96	89 + min(89, 83) = 172	99 + min(89, 86) = 185

 

이런 식으로 dp 테이블을 채워가면서 각 집의 최소 비용을 구하고, 마지막 집에서 최소값을 선택한다.

 

[코드]

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

dp = [[0] * 3 for _ in range(n)]
dp[0][0] = cost[0][0]
dp[0][1] = cost[0][1]
dp[0][2] = cost[0][2]

for i in range(1, n):
    dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
    dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
    dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])

print(min(dp[n-1][0], dp[n-1][1], dp[n-1][2]))