[백준 1149] R, G, B거리

분류 : DP

 

요구사항

이웃해 있는 집이 같은 색깔으로 중복되지 않게 최소비용으로 집 색깔 선택하기

 

풀이

n번째 집을 선택했을때 가격이 최소이려면

6가지 경우는 고려하여야 한다

현재 집 + 이웃집까지의 최소(같은 색상X)

  if(color==1) 
        ref = min(map[num][color] + func(num-1,color+2),map[num][color] + func(num-1,color+1));
    else if(color==2)
        ref = min(map[num][color] + func(num-1,color-1),map[num][color] + func(num-1,color+1));
    else if(color==3)
        ref = min(map[num][color] + func(num-1,color-1),map[num][color] + func(num-1,color-2));

 

색깔 별로 모든 경우는 고려해주고 최소를 출력한다

 

#include <iostream>
#include <string.h>
#include <queue>
//#include "windows.h"
#include <algorithm>
#include <list>

using namespace std;
int d[1010][6];
int n;
int map[1010][6];
int func(int num, int color){
    if(num==0) return 0;

    if(num==1){
        if(color==1) return map[1][1];
        else if(color==2) return map[1][2];
        else if(color==3) return map[1][3];
    }

    int &ref = d[num][color];
    if(ref!=-1){
        return d[num][color];
    }

    if(color==1) 
        ref = min(map[num][color] + func(num-1,color+2),map[num][color] + func(num-1,color+1));
    else if(color==2)
        ref = min(map[num][color] + func(num-1,color-1),map[num][color] + func(num-1,color+1));
    else if(color==3)
        ref = min(map[num][color] + func(num-1,color-1),map[num][color] + func(num-1,color-2));

    return ref;

}
int main(){
    scanf("%d",&n);
    for(int i=1 ; i <= n ; i++)
        //빨 초 파
        for(int j=1 ; j<=3; j++)
        {    scanf("%d",&map[i][j]);
        d[i][j]=-1;
        }

    int ans=987654321;
    ans=min(func(n,1) , min(func(n,2) , func(n,3)));
    cout<<ans<<endl;
}