Dahyeon's Blog

다이나믹 프로그래밍을 이용한 문제이므로 점화식을 구해야 했다.

점화식은 i가 R을 선택하는 경우(d[i][0]), G를 선택하는 경우(d[i][1]), B를 선택하는 경우(d[i][2])가 있으므로 총 점화식은 3개!

(i의 최솟값을 고르는게 최선의 경우가 아닐 수 있으므로 R,G,B를 각각 선택한 경우를 구하는 것이다.)

점화식: 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 G B

2번 집 -> R 선택 : GR, BR   중 min

             G 선택 : RG, BG   중 min

             B 선택 : RB, GB    중 min

3번 집 -> R 선택 : RGR, BGR, RBR, GBR    중 min

             G 선택 : GRG, BRG, RBG, GBG    중 min

             B 선택 : GRB, BRB, RGB, BGB     중 min

                         '

                         '

                         '

N번 집 -> .............

다음과 같은 예제를 이용해서 점화식을 이해해보자면,

1번 집 -> R(1) G(100) B(200)

2번 집 -> R 선택 : GR(100+1), BR(200+1)  

             G 선택 : RG(200+201), BG(1+201)   

             B 선택 : RB(1+101), GB(100+101)   

3번 집 -> R 선택 : RGR, BGR, RBR, GBR   

             G 선택 : GRG, BRG, RBG, GBG    

             B 선택 : GRB, BRB, RGB, BGB     

3번 집의 경우에서 취소선은 이미 2번집에서 걸러진 경우이다. 따라서 항상 2가지 경우의 수만 남으므로 점화식이 성립한다는 것을 볼 수 있다.

코드는 다음과 같다.

// RGB 거리 (실버1)
#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;

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];

}

int main() {
	int N; 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];
	}

	dynamic(N);

	cout << min(d[N][0],min(d[N][1],d[N][2]));

	return 0;
}

// 2020KB , 0ms