[백준 17404 | C++] RGB거리 2 :: 다이나믹 프로그래밍(DP)

• 문제 링크 : 17404번: RGB거리 2
• 문제 태그 : 다이나믹 프로그래밍
• 관련 문제 : 1149번: RGB거리

 

풀이

RGB거리 문제와의 차이점은

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.

조건이 추가되었다는 것입니다. 문제를 좀 더 쉽게 이해해보자면

 

집들이 원을 이루고 있으며(1번 집과 N번 집이 연속하게 만들어준다.)
이웃한 두 집들과 색이 겹치지 않아야한다.

 

 

추가된 조건은 1번과 N번 집에만 적용이 됩니다. 따라서 이 두 집만 신경쓰면 됩니다.

 

1번 집에 ⓐR을 색칠한 경우, ⓑG를 색칠한 경우, ⓒB를 색칠한 경우로 나누면 각각의 경우는

N번 집에 ⓐG/B를 색칠한 경우, ⓑR/B를 색칠한 경우, ⓒR/G를 색칠한 경우와 대응됩니다.

 

그리고 2번부터 N-1번까지의 집은 RGB거리 문제와 동일하게 다이나믹 프로그래밍을 사용하여 풀면 됩니다. 

#include <iostream>
#include <vector>

using namespace std;

const int INF = 1 << 30;

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

	int n;
	cin >> n;

	vector<vector<int>> v(n, vector<int>(3, 0));
	for (int i = 0;i < n;i++) {
		cin >> v[i][0] >> v[i][1] >> v[i][2];
	}

	vector<vector<int>> dp(n, vector<int>(3, 0));

	int ans = INF;

	for (int j = 0;j < 3;j++) {
		if (j == 0) { dp[0][0] = v[0][0]; dp[0][1] = INF; dp[0][2] = INF; }
		if (j == 1) { dp[0][1] = v[0][1]; dp[0][0] = INF; dp[0][2] = INF; }
		if (j == 2) { dp[0][2] = v[0][2]; dp[0][1] = INF; dp[0][0] = INF; }

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

		int t;

		if (j == 0) {
			dp[n - 1][1] = v[n - 1][1] + min(dp[n - 2][0], dp[n - 2][2]);
			dp[n - 1][2] = v[n - 1][2] + min(dp[n - 2][0], dp[n - 2][1]);
			t = min(dp[n - 1][1], dp[n - 1][2]);
		}
		if (j == 1) {
			dp[n - 1][0] = v[n - 1][0] + min(dp[n - 2][1], dp[n - 2][2]);
			dp[n - 1][2] = v[n - 1][2] + min(dp[n - 2][0], dp[n - 2][1]);
			t = min(dp[n - 1][0], dp[n - 1][2]);
		}
		if (j == 2) {
			dp[n - 1][1] = v[n - 1][1] + min(dp[n - 2][0], dp[n - 2][2]);
			dp[n - 1][0] = v[n - 1][0] + min(dp[n - 2][2], dp[n - 2][1]);
			t = min(dp[n - 1][1], dp[n - 1][0]);
		}

		ans = min(ans, t);
	}

	cout << ans;
}