17404 RGB 거리2 (골드 4)

1149 RGB 거리 문제에 조건 하나만 더 추가된 문제이다.

 

1149 문제는 1번은 2번과, N번은 N-1번과 다른 색이어야 하고, 1과 N을 제외한 나머지 i번째는 i-1번째 집과 i+1째 집과 다른 색이어야 하는 문제였다.

17404 문제는 1번과 N번이 다른 색이어야 하는 조건이 추가되었다.

 

 

 

이건 1149 문제와 같은 점화식을 사용한다.

d[i][0] = Min(d[i - 1][1], d[i - 1][2]) + a[0];
d[i][1] = Min(d[i - 1][0], d[i - 1][2]) + a[1];

d[i][2] = Min(d[i - 1][0], d[i - 1][1]) + a[2];

단, 1번째 집이 R을 선택했을 경우 N번째 집은 R을 선택하지 못한다는 것만 주의해주면 된다.

 

 

 

해결 방식은 1번이 무조건 R/G/B를 고르게 한 뒤에 N번은 1번이 고른 색과 다른 색을 골라서 그 두 가지 경우를 비교한 후 값이 작은 수를 저장해놓고 이를 3번 반복하는 것이다.

 

무조건 1번이 R/G/B를 고르게 하는 방법은 고를 색 빼고는 엄청 큰 값을 넣어주면 된다.

 

 

// RGB 거리 2 (골드 4)

#include <iostream>

using namespace std;

//점화식: d[i][0] = Min(d[i - 1][1], d[i - 1][2]) + a[0];
//		  d[i][1] = Min(d[i - 1][0], d[i - 1][2]) + a[1];
//		  d[i][2] = Min(d[i - 1][0], d[i - 1][1]) + a[2];

int** d;
int** RGB;
int N;

void dynamic(int x) {

	if (x == 0) return;

	dynamic(x - 1);

	d[x][0] = min(d[x - 1][1], d[x - 1][2]) + RGB[x][0];
	d[x][1] = min(d[x - 1][0], d[x - 1][2]) + RGB[x][1];
	d[x][2] = min(d[x - 1][0], d[x - 1][1]) + RGB[x][2];

		//cout << d[x][0] << " " << d[x][1] << " " << d[x][2] << endl;

}

int main() {
// 입력
	cin >> N;

	RGB = new int* [N + 1]{};
	d = new int* [N + 1]{};
	d[0] = new int[3]{};
	RGB[0] = new int[3]{};
	for (int i = 1;i < N + 1;i++) {
		d[i] = new int[3]{};
		RGB[i] = new int[3]{};
		cin >> RGB[i][0] >> RGB[i][1] >> RGB[i][2];
	}

// 풀이
	int Ans;
	int G_1 = RGB[1][1], B_1 = RGB[1][2];

	RGB[1][1] = 10000; RGB[1][2] = 10000;

	//1번집 R
	dynamic(N);
	Ans = min(d[N][1], d[N][2]);

		//cout << endl << endl;


	//1번집 G
	RGB[1][0] = 10000; RGB[1][1] = G_1; RGB[1][2] = 10000;
	dynamic(N);
	if (Ans > min(d[N][0], d[N][2])) Ans = min(d[N][0], d[N][2]);

		//cout << endl << endl;


	//1번집 B
	RGB[1][0] = 10000; RGB[1][1] = 10000; RGB[1][2] = B_1;
	dynamic(N);
	if (Ans > min(d[N][0], d[N][1])) Ans = min(d[N][0], d[N][1]);
	
		//cout << endl << endl;

	cout << Ans;

	return 0;
}

// 2020KB, 0ms