[백준] 1149번 RGB거리

1149번: RGB거리

처음엔 조건에 맞게 집을 칠할 수 있는 모든 경우의 수를 구해서

그 중 최솟값을 출력 해야하는줄 알았는데

만약에 그렇게 하면 3*(2^1000 -1)가지의 수가 나오게 된다.

절대 불가능한 숫자이므로 다시 다르게 생각해보았다.

 

R	G	B
1번째 집을 R색으로 칠하려고 할 때	1번째 집을 G색으로 칠하려고 할 때	1번째 집을 B색으로 칠하려고 할 때
2번째 집을 R색으로 칠하려고 할 때	2번째 집을 G색으로 칠하려고 할 때	2번째 집을 B색으로 칠하려고 할 때
3번째 집을 R색으로 칠하려고 할 때	3번째 집을 G색으로 칠하려고 할 때	3번째 집을 B색으로 칠하려고 할 때
...	...	...
N번째 집을 R색으로 칠하려고 할 때	N번째 집을 G색으로 칠하려고 할 때	N번째 집을 B색으로 칠하려고 할 때

 

 

이런식으로 생각을 하고 문제에 나와 있는 예제로 표현해본다면

 

 

R	G	B
26	40	83
49 + 최솟값(40, 83) = 8	60 + 최솟값(26, 83) = 86	57 + 최솟값(26, 40) = 83
13 + 최솟값(86, 83) = 96	89 + 최솟값(89, 83) = 172	99 + 최솟값(89, 86) = 185

 

이렇게 N번째 값들 중 가작 작은 값인 96이 답이 되는 것이다.

 

이대로 구현해주면 끝

#include <iostream>
#include <algorithm>
using namespace std;
long long home[1001][3] = { 0 };

int main() {
	int N;
	cin >> N;
	int R, G, B;
	cin >> R >> G >> B;
	home[0][0] = R, home[0][1] = G, home[0][2] = B;

	for (int n = 1; n < N; n++) {
		cin >> R >> G >> B;
		home[n][0] += R + min(home[n - 1][1], home[n - 1][2]);
		home[n][1] += G + min(home[n - 1][0], home[n - 1][2]);
		home[n][2] += B + min(home[n - 1][0], home[n - 1][1]);
	}

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

	return 0;
}