[백준] RGB거리 1149번 (c++)

출처 : 1149번: RGB거리 (acmicpc.net)

1149번: RGB거리

풀이 방법

dp 문제로 dp의 인덱스로 몇 번째 집인지, 자신이 선택한 색의 인덱스를 저장해 준다

기저사례로는  index 가 N-1일 땐 전 집에서 선택한 색을 제외한 두 색중 작은 값을 return한다

기저사례가 아닐시 for 문을 돌며 금지된 색이 아닐때 재귀 호출로 다음 인덱스와 선택한 색을 호출하고 그중 작은 값과 

자신이 선택한 비용을 return 하여 해결하였다.

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>


using namespace std;
int red[1001], green[1001], blue[1001];
int cost[1001][3];
// 집 인덱스 , 색 인덱스
int dp[1001][3], N, ans;
const int INF = 987654321;
// ban == 금지된 
int min_cost(int index, int ban) {
    // 기저 사례
    if (index == N-1) {
        int ret = INF;
        for (int i = 0;i < 3;i++) {
            if (ban != i) {
                ret = min(ret, cost[index][i]);
            }
        }
        return ret;
    }
    int& ret = dp[index][ban];
    if (ret != -1 ) return ret;
    ret = INF;
    for (int i = 0;i < 3;i++) {
        if (ban != i)  ret = min(ret,cost[index][i] + min_cost(index + 1, i));
    }
    return ret;
}

int main(void) {
	memset(dp, -1, sizeof(dp));
	cin >> N;
	for (int i = 0;i < N;i++) {
        cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
	}
    ans = min(min_cost(0, 0), min(min_cost(0, 1), min_cost(0, 2)));
    cout << ans;


	return 0;
}