[백준]동적 계획법1/RGB 거리/1149 풀이 JAVA

문제

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

 

출력

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

 

 

풀이(JAVA)

페인트를 칠하는 비용(cost)의 값이 아래와 같다고 하면,

(ex)cost[2][1] = 10; = 3번째 집을 초록색으로 칠하는 데 10의 비용이 듦.

color	0 빨강	1 초록	2 파랑
cost[0][color]	10	20	30
cost[1][color]	30	20	10
cost[2][color]	50	10	30

 

최소 비용의 누적합을 저장하는 dp는 아래와 같다.

(ex)dp[2][1] = 30; = 3번째 집을 초록색으로 칠하는 비용 30 + 2번째 집을 (초록색 제외한 색 중 최소 비용) 파란 색으로 칠하는 비용 10 + 1번째 집을 (파란색 제외한 색 중 최소 비용) 빨간 색으로 칠하는 비용 10

color	0 빨강	1 초록	2 파랑
dp[0][color]	10	20	30
dp[1][color]	50(20 + 30)	30(10 + 20)	20(10 + 10)
dp[2][color]	70(10 + 10 + 50)	30(10 + 10 + 10)	60(10 + 20 + 30)

즉, n번째 집을 빨간 색으로 칠할 때,

dp[n][0] = Math.min(dp[n - 1][1], dp[n - 1][2]) + cost[n][color];라는 점화식을 세울 수 있다.

(n번째 집을 빨간 색으로 칠할 때, 1번째 집부터 n번째 집까지의 최솟값 비용의 누적합 =

빨간색이 아닌 색들 중의 최소 비용 + n번째 집을 빨간색으로 칠한 비용)

 

---

이해하기 어렵다고 생각했는데 알고보니... 그렇게 어렵진 않았다.

그냥 엄청 꼬아꼬아 생각한 듯... 넓게 보자.