[Baekjoon,17404] RGB거리 2

원형으로 되어있는 구조에서 집들의 색상을 어떻게 최소 비용으로 조합할지 찾아야 한다. 원형으로 되어있다는 것은 첫 번째 집과 마지막 집이 이어져 있다는 것이다. 이 때문에 첫 번째 집의 색상이 마지막 집의 색상에 영향을 준다. 따라서 첫 번째 색상이 어떻게 되어있냐에 따라 나머지 집의 색상을 선택하면 된다. 부분 문제를 다음과 같이 정의할 수 있다.

• $dp(here,prevColor,firstColor)=$현재 $here$번째 집이고 바로 앞의 집의 색이 $prevColor$이며, 첫 번째 집의 색상이 $firstColor$일때 나머지 집을 칠하는 최소 비용

이에 대한 구현은 아래에서 볼 수 있다. 첫 번째 집의 색을 먼저 고르고 $dp()$ 함수를 호출하고 있다.

#include <iostream>
#include <cstring>
using namespace std;

const int INF=987654321;
const int MAX_N=1000;

int N;
int cost[MAX_N][3];
int cache[MAX_N][3][3];

int dp(int here, int prevColor, int firstColor)
{
    // 색상 선택이 완료된 경우 
    if(here==N)
        return 0;
    
    int& ret=cache[here][prevColor][firstColor];
    if(ret!=-1)
        return ret;
    
    ret=INF;
    for(int color=0;color<3;++color)
        if(color!=prevColor)
        {
            // 현재 선택할 색상의 집이 마지막 집인데 
            // 첫 번째 집과 색이 같은 경우 
            if(here==N-1 && firstColor==color)
                continue;
            ret=min(ret,dp(here+1,color,firstColor)+cost[here][color]);
        }
    
    return ret;
}

int main()
{
    cin>>N;
    for(int i=0;i<N;++i)
        cin>>cost[i][0]>>cost[i][1]>>cost[i][2];
    memset(cache,-1,sizeof(cache));
    
    int ret=INF;
    // 첫 번째 집의 색을 먼저 고른다. 
    for(int color=0;color<3;++color)
        ret=min(ret,dp(1,color,color)+cost[0][color]);
    
    cout<<ret<<endl;
    return 0;
}