[BOJ] 17404 RGB거리 2

DFS로 접근할 경우 시간 초과가 발생하였다.
DP를 이용하여 해결하였다.
DP값을 잘 잡는게 중요한데 int rgb2DP[i][j] = k 로 설정하였고
이 의미는 i번째 집에 j번째 색으로 색칠하였을 경우 최소 비용은 k값 이다.라는 가정이다.
자세한 해석은 주석에 있다.

#include <iostream>
#include <functional>

using namespace std;
int rgbDat[1001][3] = {0,};
int rgb2DP[1001][3] = {0,};
int main()
{
   int rgbHouse = 8;
   int minRgbCost = 2e9;
    cin>>rgbHouse;
    
    for(int i=1; i<=rgbHouse; i++)
    {
        int a,b,c=0;
        cin>>a>>b>>c;
        rgbDat[i][0] = a;
        rgbDat[i][1] = b;
        rgbDat[i][2] = c;
    }
    
   auto rgbCalc = [&](){
   for(int i=3; i<=rgbHouse; i++)
   {
       for(int j=0; j<3; j++)
       {
       //2번째 집부터 N-1번째 집이 i라고 가정하면 i-1,i+1번째 집과 색이 달라야 한다.   
       //따라서 현재 색칠하려는 집이 j일 경우 이전 집의 색은 j가 아니어야한다. 
       //이전 집까지의 최소 색칠 비용 + 현재 색칠하려는 비용
           if(j==1)
               rgb2DP[i][j] = min(rgb2DP[i-1][0],rgb2DP[i-1][2])+rgbDat[i][j];
           else if(j==0)
               rgb2DP[i][j] = min(rgb2DP[i-1][1],rgb2DP[i-1][2])+rgbDat[i][j];
           else if(j==2)
               rgb2DP[i][j] = min(rgb2DP[i-1][0],rgb2DP[i-1][1])+rgbDat[i][j];
       };
   };
};

   int rgbANS = 2e9;
   //1이 R경일 경우 N번은 G or B여야한다.
   //첫번째 집이 R이니까 2번째 집은 무조건 G아니면 B여야한다.
   //따라서 미리 최소비용 계산이 가능하다.
   //첫번째 집이 R이므로 2번째 집은 R이 절대 올 수 없으므로 
   //3번째 집을 칠 할 경우 2번째 집이 R로 색칠한 경우의 수가 
   //올 수 없도록 큰 값으로 설정한다.
   rgb2DP[2][0] = 2e9;
   rgb2DP[2][1] = rgbDat[1][0]+ rgbDat[2][1];
   rgb2DP[2][2] = rgbDat[1][0]+ rgbDat[2][2];
   rgbCalc();
   //첫번째 집이 R이므로 마지막 집은 G,B여야 하므로
   //마지막 집을 G,B로 색칠하였을 경우 최소값을 계산한다.
   int tmpMin = min(rgb2DP[rgbHouse][1],rgb2DP[rgbHouse][2]);
   rgbANS = min(rgbANS,tmpMin);

   //1이 G경일 경우 N번은 R or B여야한다.
   rgb2DP[2][0] = rgbDat[1][1]+ rgbDat[2][0];
   rgb2DP[2][1] = 2e9;
   rgb2DP[2][2] = rgbDat[1][1]+ rgbDat[2][2];
   rgbCalc();
   tmpMin = min(rgb2DP[rgbHouse][0],rgb2DP[rgbHouse][2]);
     rgbANS = min(rgbANS,tmpMin);

   //1이 B경일 경우 N번은 R or G여야한다.
   rgb2DP[2][0] = rgbDat[1][2]+ rgbDat[2][0];
   rgb2DP[2][1] = rgbDat[1][2]+ rgbDat[2][1];
   rgb2DP[2][2] = 2e9;
   rgbCalc();
   tmpMin = min(rgb2DP[rgbHouse][0],rgb2DP[rgbHouse][1]);
     rgbANS = min(rgbANS,tmpMin);
    
    cout<<rgbANS<<endl;
    return 0;
}