[알고리즘] 백준 17404번: RGB거리 2 (C++), 의도적 코드

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

17404번: RGB거리 2

지난번에 풀었던 RGB 거리 문제와 다른 조건이 딱 하나 걸려있다.

(RGB 거리 https://draw-code-boy.tistory.com/51)

1번 집과 N번 집의 색깔이 같으면 안 된다.

---

이 조건을 맞춰주기 위해 초기값(1번 집)에서 최솟값이 나오는 인덱스를 구하고, DP가 끝난 후에 최솟값이 나오는 인덱스 값(1번 집 색깔)을 제외한 색깔 중에 DP 최솟값을 구하면 답이 될 거라 생각했다.

하지만, 다음과 같은 반례를 만들어 볼 수 있었다.

3
100 100 100
100 1 100
100 100 1

이러한 케이스의 경우에 1번 집의 색깔 중 무엇을 최솟값으로 잡아야 할지 판단할 수 없다.

[오류 코드]

#include <iostream>
#include <cmath>
#define MAX 1001
using namespace std;

int N;
int cache[MAX][3];
int rgb[MAX][3];

int minIdx(int zero, int one, int two) {
	int value = min(zero, min(one, two));

	if (value == zero) {
		return 0;
	}
	else if (value == one) {
		return 1;
	}
	else if(value == two) {
		return 2;
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> rgb[i][0] >> rgb[i][1] >> rgb[i][2];
	}

	int startIdx = minIdx(rgb[1][0], rgb[1][1], rgb[1][2]);
	cache[1][0] = rgb[1][0];
	cache[1][1] = rgb[1][1];
	cache[1][2] = rgb[1][2];

	for (int i = 2; i <= N; i++) {
		cache[i][0] = rgb[i][0] + min(cache[i - 1][1], cache[i - 1][2]);
		cache[i][1] = rgb[i][1] + min(cache[i - 1][0], cache[i - 1][2]);
		cache[i][2] = rgb[i][2] + min(cache[i - 1][0], cache[i - 1][1]);
	}

	if (startIdx == 0) {
		cout << min(cache[N][1], cache[N][2]);
	}
	else if (startIdx == 1) {
		cout << min(cache[N][0], cache[N][2]);
	}
	else {
		cout << min(cache[N][1], cache[N][0]);
	}
	return 0;
}

---

솔루션

다음 솔루션을 참고했다.

(https://cocoon1787.tistory.com/498)

이 솔루션에서는 3가지 색깔 중에 의도적으로 하나의 색깔을 최솟값으로 만들어서 DP를 한 다음 최솟값이 된 인덱스를 제외한 DP를 한 두 색깔 중에 최솟값을 선택하도록 하였다.

>> 의도적으로 하나의 색깔을 골라 최솟값으로 만들었기 때문에 코딩한 사람이 무슨 인덱스가 최솟값이 되는지 설정하게 하는 것.

1번 집에서 무슨 색을 썼는지 코딩한 사람이 알게 하도록 만든 '의도적 코드'가 이번 문제의 핵심이다.

 

#include <iostream>
#include <cmath>
#define MAX 1001
#define MAX2 1000000
using namespace std;

int N;
int cache[MAX][3];
int rgb[MAX][3];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> rgb[i][0] >> rgb[i][1] >> rgb[i][2];
	}

	int result = MAX2;
	
	for (int color = 0; color <= 2; color++) { // 의도적으로 하나를 최솟값으로 하기위해
		for (int i = 0; i <= 2; i++) {
			if (i == color) {
				// 의도적 최솟값
				cache[1][i] = rgb[1][i];
			}
			else {
				// 의도적 최댓값
				cache[1][i] = MAX2;
			}
		}

		for (int i = 2; i <= N; i++) {
			cache[i][0] = rgb[i][0] + min(cache[i - 1][1], cache[i - 1][2]);
			cache[i][1] = rgb[i][1] + min(cache[i - 1][0], cache[i - 1][2]);
			cache[i][2] = rgb[i][2] + min(cache[i - 1][0], cache[i - 1][1]);
		}

		for (int i = 0; i <= 2; i++) {
			if (i == color) {
				// 어느 색이 최솟값을 유발하도록 설정해두었기 때문에
				// i가 color일 경우 패스
				continue;
			}
			else {
				result = min(result, cache[N][i]);
			}
		}
	}

	cout << result;
	return 0;
}

---

느낀 점

의도적 코드(?)는 처음 알게 된 솔루션이다. 나중에 접근하는 방법에 써먹을 수 있을 거 같다.

무조건 업 솔빙 해야 할 문제