[C++] 백준 17404번: RGB 거리 2

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

17404번: RGB거리 2

 

3차원 DP를 사용하여 이 문제를 해결하였다.

 

> 발상

처음 혹은 마지막 집을 제외하면, 영향을 미치는 범위는 인접한 집뿐이라는 것을 알 수 있다. 이를 통해 O(N)의 반복과 같은 접근법을 사용할 수 있다고 판단하였다.

그리고 중요한 요소가 있는데, 바로 0, N-1번째 집이다. 만약 짜게 될 코드가 0부터 시작해서 N-1에 도달하는 식이라면, 분명히 인덱스가 0인 집이 나중에 영향을 미치게 되므로 이 정보를 저장해야한다.

이를 통해 짜낸 것이 3차원 DP이다. 다만, 코드를 N-1부터 0으로 진행되는 top-bottom DP를 사용하였다는 점에 유의한다.

dp[index][color][first] = min(dp[index+1][another color1][first], dp[index+1][another color2][first])

 

> 풀이

DP는 사실상 발상이 전부이다. 코드는 아래에 있다.

 

#include <iostream>
#define INF 1000001
using namespace std;

int N;
int costs[1000][3];
int dp[1000][3][3]; // index, color, first

int getDp(int index, int color, int first) {
	// dp에 값이 아직 설정되지 않았을 경우
	if (dp[index][color][first] == 0) {
		if (index == N - 1) {
			if (first == color) dp[index][color][first] = INF;
			else dp[index][color][first] = costs[index][color];
		}
		else {
			dp[index][color][first] = min(
				getDp(index + 1, (color + 1) % 3, first),
				getDp(index + 1, (color + 2) % 3, first)
			) + costs[index][color];
		}
	}

	return dp[index][color][first];
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	
	// Set costs
	int i;
	for (i = 0; i < N; i++)
		cin >> costs[i][0] >> costs[i][1] >> costs[i][2];
	
	// Set minCost using DP
	int minCost = INF;
	for (i = 0; i < 3; i++)
		minCost = min(minCost, getDp(0, i, i));
	cout << minCost;

	return 0;
}

 

> Advanced

bottom-up 형식의 코드를 짜면 매우 효율적인 풀이를 할 수 있다. 사실 0~N-1 순서로 진행하면서, 바로 직전의 정보만을 가지고 문제를 풀 수 있다.

 

#include <iostream>
#define INF 1000001
using namespace std;

int N;
int dp1[3][3]; // color, first
int dp2[3][3];

int main()
{
	int i, j, k;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	
	// Initialize dp
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			dp1[i][j] = INF;
		}
	}

	int costs[3];
	cin >> costs[0] >> costs[1] >> costs[2];
	for (i = 0; i < 3; i++) dp1[i][i] = costs[i];

	// Solution
	for (i = 1; i < N; i++) {
		cin >> costs[0] >> costs[1] >> costs[2];

		// Set dp2
		for (j = 0; j < 3; j++) {
			for (k = 0; k < 3; k++) {
				dp2[j][k] = min(dp1[(j + 1)%3][k], dp1[(j + 2)%3][k]) + costs[j];
			}
		}

		// Copy dp1 <- dp2
		for (j = 0; j < 3; j++) {
			for (k = 0; k < 3; k++) {
				dp1[j][k] = dp2[j][k];
			}
		}
	}

	// Print the result
	int minCost = INF;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			if (i == j) continue; // "1번 집, N번 집의 색이 같지 않아야 한다."
			minCost = min(minCost, dp1[i][j]);
		}
	}
	cout << minCost;

	return 0;
}