백준 1149 RGB거리 c++ // 재귀dp, 추가정보 필요시 해결방법

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

 

1. 의사코드

1. 완탐 -> 3C1 을 N번반복 -> 3^1000 -> 불가

2. dp? 

3. 상태 : [idx][색깔] 1000(n개)*3(빨,노,파)에 가능!

3.5 값 : 그 상태일때, 비용의 최소값

4. 완탐기반으로, 위에서 칠한색을 제외한 2개중 최소값을 dp에 저장함.

 

2. 추가정보 필요시 해결방법

위에서 무슨색을 칠했는지 알아야하기때문에 , b[idx] 배열에 기록해둠.

 

3. 전체코드

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

int n, k,dp[1004][3],a[1004][3];
int b[1004]; //해당 idx에 어느색을 칠했는지

int dfs(int idx, int color) {
	//기저사례
	//!조건불만족하면 리턴! 이 return이 먼저와야함!! -> 그래야 배제가능.
	// 안그러면, 조건불만족 인데 idx==n인 경우도 유효한 경우로 카운팅됨.
	if (idx == n) {
		return 0;
	}
	
	if (dp[idx][color] != -1) return dp[idx][color];

	dp[idx][color] = 987654321;
	b[idx] = color;
	vector<int> tmp; //색칠가능한 색깔
	for (int i = 0; i < 3; ++i) {
		if (i == color) continue;
		tmp.push_back(i);
	}
	//위에서 칠한색 빼고 2개 탐색
	dp[idx][color] = min(dfs(idx+1, tmp[0]) + a[idx][tmp[0]], 
		dfs(idx + 1, tmp[1]) + a[idx][tmp[1]]);

	return dp[idx][color];
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	memset(dp, -1, sizeof(dp));
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int q, w,e;
		cin >> q>>w>>e;
		a[i][0] = q;
		a[i][1] = w;
		a[i][2] = e;
	}

	//0번 가방을 담는경우, 안담는경우로 시작
	int q = dfs(0, 0);
	int w = dfs(0, 1);
	int e = dfs(0, 2);
	int ret = 987654321;
	ret = min(ret, q);
	ret = min(ret, w);
	ret = min(ret, e);

	cout << ret;
	return 0;
}