BJ1149 RGB거리

풀이

백트래킹 & DP

1. 0번째 집부터 차례대로 N-1 까지 칠한다.

   (재귀함수의 기저조건이 n>=N return 0이 된다.)

2. k번째 집을 칠할 때 이전에 칠한 색을 prev로 받고 prev일 때 k번째 칠할 수 있는 경우의 최솟값이 DP에 있는지 확인한다.

   1. 있다면 그 값을 return한다.
   2. 없다면 백트래킹으로 현재 비용+다음 최솟값 중 가장 작은 값을 구해서 기록하고 return한다.

3. 최소 결과를 출력한다.

코드

//! 2020.03.12
// TODO BJ1149_RGB거리.cpp
#include<cstdio>
using namespace std;

const int MAX = 1050;
const int INF = 987654321;
int N;
int myMap[MAX][3];
int DP[3][MAX];

int getMin(int n1,int n2){
    if(n1<n2) return n1;
    else return n2;
}

int getResult(int prev,int idx){
    if(idx>=N) return 0;

    int& ret = DP[prev][idx];
    if(ret!=-1) return ret;

    ret = INF;
    if(idx==0){
        for(int i=0;i<3;i++){
            ret = getMin(ret,myMap[idx][i]+getResult(i,idx+1));
        }
    }else{
        for(int i=0;i<3;i++){
            if(i!=prev)
                ret = getMin(ret,myMap[idx][i]+getResult(i,idx+1));
        }
    }

    // printf("idx : %d, ret : %d\n",idx,ret);
    return ret;
}

int main(){
    scanf("%d",&N);

    for(int i=0;i<N;i++){
        for(int j=0;j<3;j++){
            scanf("%d",&myMap[i][j]);
            DP[j][i] = -1;
        }
    }

    printf("%d\n",getResult(0,0));

    return 0;
}

실수

큰 실수는 없었지만 DP를 섞은 재귀를 설계하는 데에 시간이 꽤 걸렸다.