[백준 17404] RGB 거리 2

문제

www.acmicpc.net/problem/17404

17404번: RGB거리 2

 

풀이

1. 연속된 세 집의 색깔을 결정하는게 아니라 연속된 두 집의 색을 결정해간다고 생각하면 다른 집들과 조건이 다른 첫 집의 색을 고정했을 때, 나머지 집의 가능한 색을 찾아 비용을 최소화하는 방법으로 생각할 수 있습니다.

 

2. "dp[cur][precolor] = 현재 cur번째 집의 색을 결정하고 있으며, 바로 전 집을 precolor로 칠했을 때 모든 집을 칠하는 최소 색칠 비용"이라고 정의하면 상태 전이는 아래와 같습니다. (고정한 첫 집 색 : first)

 

i : 현재 cur번째 집을 색칠할 색이며, 색은 세 가지 이므로 i의 구간은 [0, 3) 입니다. 이 때 마지막 집의 색은 그 전의 집, 첫 번째 집의 색과 달라야하는걸 예외처리해주면 해결할 수 있습니다.

   $dp[cur][pre] = min(dp[cur][pre] , c[cur][i]) (cur = n - 1) (단, i != first, i != precolor)$

   $= min(dp[cur][pre] , dp[cur+1][i] + c[cur][i] ) (cur  != n - 1) (단, i != precolor)$

 

코드

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
int n, first, co[1001][3], dp[1001][3], ans;

int go(int c, int p) {
	int& ret = dp[c][p];
	if (ret != -1) return ret;
	ret = inf;
	if (c == n - 1) { // 마지막 집일 때
		for (int i = 0; i < 3; i++)
			if (i != p && i != first) // 첫 번째 집, 마지막 바로 전 집과 색이 다를 때만
				ret = min(ret, co[c][i]);
	}
	else {
		for (int i = 0; i < 3; i++)
			if (i != p) // 바로 전 집과 색이 다를 때만
				ret = min(ret, go(c + 1, i) + co[c][i]);
	}
	return ret;
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			cin >> co[i][j];
	ans = inf;
	for (int i = 0; i < 3; i++) {
		memset(dp, -1, sizeof(dp));
		first = i;
		ans = min(ans, go(1, i) + co[0][i]);
	}
	cout << ans;
}