문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
우선 위의 3가지 조건에 집중했다. 간단히 요약하자면 인접하는 두 집의 색이 서로 달라야 한다는 것이다. 인접하는 두 집의 색이 서로 다르면서 페인트 비용이 최소가 되어야 한다는 것이 이 문제의 핵심이다.
우선 모든 경우의 수를 따지는 접근방법을 생각했다. 즉, 칠할 수 있는 색의 모든 경우의 수를 따진 후 그 중 페인트칠 값이 최소가 되는 경우 하나를 차출하는 접근이었다. 그러나 이 경우는 집의 수가 많아짐에 따라 경우의 수가 급격히 많아져 제한된 시간 내에 해답을 내놓기가 어려웠다.
따라서 문제를 나누어서 해결해야 했다. 순서대로 각 집을 칠해 나가면서 각각의 색을 칠할 경우의 최소 가격을 배열에 저장해 나가는 방법을 생각했다.
//BOJ 1149
#include <iostream>
using namespace std;
// 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
// N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
// i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
// --> 집을 세가지 색으로 칠할 때 각각의 최소값을 저장해나간다.
int house[1001][3]; // 0:RED, 1:GREEN, 2:BLUE
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// 집의 수 N
int N;
cin >> N;
for(int i=1; i<=N; i++){
int R, G, B;
cin >> R >> G >> B; //0:R, 1:G, 2:B
house[i][0] = min(house[i-1][1],house[i-1][2]) + R;
house[i][1] = min(house[i-1][2],house[i-1][0]) + G;
house[i][2] = min(house[i-1][0],house[i-1][1]) + B;
}
cout << min(house[N][0], min(house[N][1], house[N][2]) );
return 0;
}
여기서 핵심이 되는 내용은 반복문 안의 내용인데 다음과 같다.
for(int i=1; i<=N; i++){
int R, G, B;
cin >> R >> G >> B; //0:R, 1:G, 2:B
house[i][0] = min(house[i-1][1],house[i-1][2]) + R;
house[i][1] = min(house[i-1][2],house[i-1][0]) + G;
house[i][2] = min(house[i-1][0],house[i-1][1]) + B;
}
즉, 모든 경우의 수를 따지는 것이 아니라 처음부터 색을 하나 하나 칠해가며 경우의 수를 따지는 것이다. 그럼 다음과 같은 규칙을 확인할 수 있다.
이 규칙을 적용 할 경우 집이 최대 1000개가 존재 한다고 하더라도 약 3000번의 연산을 거치면 최소값을 구하는 것이 가능하다.