문제 간략 설명

RGB거리에 집이 N개 있고, 집을 빨강, 초록, 파랑 중 하나로 칠해야 한다. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 하고, N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다. 각 집을 칠하는 비용의 최솟값을 구한다.

풀이 방법

DP를 사용한다. 저장해야 하는 정보는 시작 집 색, 현재 집 색, 현재까지 비용이다.

점화식은 RGB 순서대로 0, 1, 2이다. i번째 집까지 비용 계산식은 i번째 R로 칠하는 비용은 이전 집을 G, B로 칠하고 이번 집을 R로 칠하는 비용이다.

dp[i][0] = min(dp[i - 1][1] + R[i], dp[i - 1][2] + R[i])
dp[i][1] = min(dp[i - 1][0] + G[i], dp[i - 1][2] + G[i])
dp[i][2] = min(dp[i - 1][0] + B[i], dp[i - 1][1] + B[i])

첫 집 색에 대해서 각 dp를 돌리고 마지막 집이 첫 집과 겹치지 않는 색 중 작은 것을 선택한다.

비용에 대해선 최대가 1000이므로 첫 집 색으로 선택하지 않을 부분은 1001로 초기화하면 자동으로 pruning된다.

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int N;
int dp[1000][3][3];
vector<int> R, G, B;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;

	R.resize(N);
	G.resize(N);
	B.resize(N);

	for (int i = 0; i < N; i++)
		cin >> R[i] >> G[i] >> B[i];

	// 첫번째 집 R
	dp[0][0][0] = R[0];
	dp[0][1][0] = 1001;
	dp[0][2][0] = 1001;

	// 첫번째 집 G
	dp[0][0][1] = 1001;
	dp[0][1][1] = G[0];
	dp[0][2][1] = 1001;

	// 첫번째 집 B
	dp[0][0][2] = 1001;
	dp[0][1][2] = 1001;
	dp[0][2][2] = B[0];

	for (int start = 0; start < 3; start++) {
		for (int i = 1; i < N; i++) {
			dp[i][0][start] = min(dp[i - 1][1][start] + R[i], dp[i - 1][2][start] + R[i]);
			dp[i][1][start] = min(dp[i - 1][0][start] + G[i], dp[i - 1][2][start] + G[i]);
			dp[i][2][start] = min(dp[i - 1][0][start] + B[i], dp[i - 1][1][start] + B[i]);
		}
	}

	int ans = 1e9;

	for (int start = 0; start < 3; start++) {
		for (int end = 0; end < 3; end++) {
			if (start == end) continue;
			ans = min(ans, dp[N - 1][end][start]);
		}
	}

	cout << ans << endl;

	return 0;
}

Key Points

notepad