[1149] RGB거리

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

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

코드1 (오답)

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <stack>

using namespace std;

int N;
int house[1001][4];
int cost[4];
long long minn = 9999999999999;

void rgb(int n, int next, int sum){

	sum += house[n][next];
	
	if(sum > minn){
		return;
	}
	
	if(n == N-1){
		if(minn > sum){
			minn = sum;
		}
		return;
	}

	if(next == 0){
		rgb(n+1, 1, sum);
		rgb(n+1, 2, sum);
	}
	else if(next == 1){
		rgb(n+1, 0, sum);
		rgb(n+1, 2, sum);
	}
	else if(next == 2){
		rgb(n+1, 0, sum);
		rgb(n+1, 1, sum);
	}
}

int main() {

	cin >> N;
	for(int i=0; i<N; ++i){
		for(int j=0; j<3; ++j){
			cin >> house[i][j];
		}
	}

	rgb(0, 0, 0);
	rgb(0, 1, 0);
	rgb(0, 2, 0);

	cout << minn;
	
  return 0;
}

처음에 동적 계획법을 무시하고 이렇게 짜봤다. 하지만 당연히 시간초과....

몇번을 더 생각한 후 결국 힌트를 봐버렸다...

코드2 (정답)

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <stack>

using namespace std;

int N;
int house[1001][4];
int cost[4];

int main() {

	cin >> N;
	for(int i=1; i<=N; ++i){
		for(int j=0; j<3; ++j){
			cin >> cost[j];
		}

		house[i][0] = min(house[i-1][1], house[i-1][2]) + cost[0];
		house[i][1] = min(house[i-1][0], house[i-1][2]) + cost[1];
		house[i][2] = min(house[i-1][1], house[i-1][0]) + cost[2];
	}

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

	
  return 0;
}

dp의 핵심은 문제를 쪼개는 것이다.

먼저 윗줄에서의 최소값에다가 자신의 값을 더하고 또 아래로 내려가서 이 동작을 반복하고 하다보면

최소값을 구할 수 있을 것이다.