문제

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

---

풀이

예제를 하나씩 살펴보며 그리디로 최적해를 구할 수 있는지 먼저 생각해보았다.

1부터 n번째 집까지, 인접한 집과 다른 색상이면서 비용은 최소가 되는 색상을 하나씩 선택하였다.

1~4번 예제까지는 그리디로 답이 나왔지만, 5번 예제는 그렇지 않았다. 즉, 바로 이전 집과 색상이 겹치지 않으면서 비용이 최소가 되는 색상을 선택해나가는 그리디로는 최적해를 구할 수 없는 문제이다.

이럴 때는 가능한 모든 경우의 수를 고려하여 최적해를 구하는 DP를 떠올릴 수 있다.

DP는 문제가 다음과 같은 조건을 만족시킬 때 적용할 수 있다.

1. 최적 부분 구조 (Optimal substructure)
   큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping subproblem)
   동일한 작은 문제를 반복적으로 해결한다.

부분 문제를 어떻게 정의해야 할까?

dp[i] = 1~i번째 집까지 가능한 모든 경우의 수 (인접한 집과 다른 색상인 경우) 를 고려하여 최소한의 비용을 저장

이렇게 정의하면, dp[n]을 구할 때 가능한 모든 경우의 수가 최대 3 * 2 * 2 * ... * 2 = 3 * 2^999 가지 나오는데, 이 중에서 최솟값을 구해야 하므로 시간복잡도는 O(2^n) 이다. (n은 최대 1000)

그리고 dp[n]을 구할 때 이전에 계산했던 작은 문제들의 해를 이용해야 하는데, 그렇지 않고 그냥 1~n번째 집까지 가능한 모든 경우의 수 중에서 최소 비용을 구하므로 이건 DP가 아니라 브루트포스라고 볼 수 있다,,

부분 문제를 어떻게 정의해야 할지 모르겠어서 다른 풀이를 참고했다.

답안

dp 테이블에 현재 집을 어떤 색상으로 칠했는지도 같이 저장해야 한다. 왜냐하면 그에 따라 다음 집에 칠할 색상이 달라지기 때문이다.

따라서 dp[1001][3]로 선언하고 다음과 같이 dp 테이블을 정의할 수 있다.

dp[i][0] : i번째 집을 R로 칠할 때의 최소 비용
dp[i][1] : i번째 집을 G로 칠할 때의 최소 비용
dp[i][2] : i번째 집을 B로 칠할 때의 최소 비용

dp[i]가 R로 칠해지기 위해서는 이전 집이 G 또는 B여야 하고,
G로 칠해지기 위해서는 이전 집이 R 또는 B여야 하고,
B로 칠해지기 위해서는 이전 집이 R 또는 G여야 한다.

이를 바탕으로 반복문을 구현하면 다음과 같다.

for(int i = 1; i <= n; i++){
	cin >> cost[0] >> cost[1] >> cost[2];
	dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[0];
	dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[1];
	dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[2];
}

C++ 코드

#include <iostream> 
#include <vector> 
#include <string>
#include <algorithm>
using namespace std;

const int COLOR_NUM = 3; 
const int HOUSE_NUM = 1001; 
int cost[COLOR_NUM]; 
int dp[HOUSE_NUM][COLOR_NUM]; 

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);
	
	dp[0][0] = 0; 
	dp[0][1] = 0; 
	dp[0][2] = 0; 

	int n; 
	cin >> n;

	for(int i = 1; i <= n; i++){
		cin >> cost[0] >> cost[1] >> cost[2];

		// i번째 집을 R, G, B로 칠할 때의 최소 비용 저장 
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[2];
	}

	// N번째 집까지 칠했을 때, 최소 비용 출력 
	cout << min(min(dp[n][0], dp[n][1]), dp[n][2]); 
	
	return 0;
}