[백준 1149] RGB거리

세우자. 점화식.

 

비용의 최솟값을 구하는게 목적이다.

 

확실하게 할 것이 하나있다.

우리는 1~n번째 집들이 각각 어떤 색으로 칠해지는지 궁금하지 않다.

얼마의 비용이 필요한지 궁금하다.

 

그러므로, 이 문제에선 우리는 세 개의 DP 배열이 필요하다.

빨간색을 선택했을 때 총 비용의 최솟값, 초록색을 선택했을 때 총 비용의 최솟값, 파란색을 선택했을 때 총 비용의 최솟값을 저장할 배열이다.

 

자세하게 설명하면, dp[n][빨간색]의 값은 n번째 집을 빨간색으로 칠했을 때 총 비용의 최솟값이라고 하자.

그렇다면, n번째 집을 빨간색으로 칠할 때 총 비용의 최솟값은 n번째 집을 빨간색으로 칠하는 비용 + (n-1번째 집이 초록색일 때 총 비용의 최솟값)과 (n-1번째 집이 파란색일 때 총 비용의 최솟값) 중 작은 값이라고 봐도 될까 ? 

 

식으로 표현하게 되면, 

dp[n][빨간색] = min(dp[n-1][초록색], dp[n-1][파란색]) + cost[n][빨간색]

이라고 해도 될까 ?

 

된다.

우리는 n번 집을 빨간색으로 칠할 때, 1 ~ n-2번이 어떤 색으로 칠해져 있는지 궁금하지 않다.

그저 n-1번째 집이 초록색 또는 파란색일 때 드는 전체 비용의 최솟값만 알면 n번 집을 빨간색으로 칠할 때 총 비용의 최솟값을 알 수 있다.

 

결국 점화식을

dp[n][빨간색] = min(dp[n-1][초록색], dp[n-1][파란색]) + cost[n][빨간색]

dp[n][초록색] = min(dp[n-1][빨간색], dp[n-1][파란색]) + cost[n][초록색]

dp[n][파란색] = min(dp[n-1][빨간색], dp[n-1][초록색]) + cost[n][파란색]

으로 정리할 수 있다.

 

자, 밑의 예제를 통해 세 개의 DP배열을 어떻게 사용하는지 알아보자.

	R	G	B
1	26	40	83
2	49	60	57
3	13	89	99

각각의 집을 색칠할 때마다 드는 비용이 위와 같다고 하자.

1번 집은 첫번째 집이기 때문에 어떤 색으로 칠하든 그 값이 곧 총 비용의 최솟값이 된다. DP의 첫번째 행을 업데이트 하자.

	R	G	B
dp[1]	26	40	83
dp[2]
dp[3]

2번 집을 빨간색으로 칠하려고 한다. 규칙에 의해 1번 집은 초록색 or 파란색이 되어야 한다.

때문에 dp[2][R]은 dp[1][G]과 dp[1][B] 중 더 작은 값 + 2번 집을 빨간색으로 칠하는 비용이다.

 

마찬가지로 2번 집을 초록색인 경우(dp[2][G])는 dp[1][R]과 dp[1][B] 중 더 작은 값 + 2번 집을 초록색을 칠하는 비용이다.

 

2번 행을 채우자.

	R	G	B
dp[1]	26	40	83
dp[2]	89(=49 + 40)	86(=26+60)	83(=26+57)
dp[3]

 

3번 집을 칠해보자.

우리는 2번 집을 초록색으로 칠했을 때 총 비용의 최솟값(dp[2][G])과 파란색으로 칠했을 때 총 비용의 최솟값(dp[2][B])을 알고 있다.

따라서 3번 집을 빨간색으로 칠할 때 총 비용의 최솟값은 dp[2][G]와 dp[2][B] 중 더 작은 값 + 3번 집을 빨간색으로 칠하는 비용이다.

같은 매커니즘으로 초록색과 파란색의 경우도 구하자.

	R	G	B
dp[1]	26	40	83
dp[2]	89	86	83
dp[3]	96(=83 + 13)	172(=83+89)	185(=86+99)

결국 1, 2, 3번 집을 칠하는데 드는 총 비용의 최솟값은 96, 172, 185 중 가장 작은 값인 96이 된다.

 

이해가 안될 수도 있다. 나도 그랬다.

dp[n][R]의 의미를 n번째 집을 빨간색으로 칠할 때 전체 비용의 최솟값이라고 설정했을 때,

dp[n-1][R], dp[n-1][G], dp[n-1][B]의 의미를 생각하고 이것들을 이용하여 dp[n][R]을 만드는 연습을 해보자.

 

이 문제는 n-1번째만 보면 되지만, n-2번째나 n-3번째를 봐야하는 경우도 있으니.. 점화식 만드는 연습을 하자.

 

이해됐으면 코딩하자.

#include <bits/stdc++.h>

using namespace std;

// 0 : R, 1 : G, 2 : B
int cost[1001][3];
int dp[1001][3];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) cin >> cost[i][0] >> cost[i][1] >> cost[i][2];

	for (int i = 1; i <= n; i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
	}

	cout << min({ dp[n][0],dp[n][1],dp[n][2] });

	return 0;
}

아무 생각 없이 int형 배열로 통과하긴 했는데.. 만약 틀렸을 때는 long long 타입으로 바꿔야하는지부터 의심해보자.