백준 17404, RGB거리 2

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1 

3
26 40 83
49 60 57
13 89 99

예제 출력 1 

110

 

 단순하게 이웃하는 것 뿐만 아니라 처음과 끝 집의 색이 달라야 한다는 조건이 추가된 문제이다. 나는 이 문제를 9 가지의 경우를 저장해야 하는 문제(r - r, r - g, r - b, g - r, g - g, g - b, b - r, b - g, b - b )로 보았다.(ex : r - g는 첫 집이 빨간 색이고 마지막 집이 초록색이라는 뜻이다.) 조건 때문에 집이 2 개인 경우, 3 개인 경우, 그외인 경우로 나누어 배열을 채워야 한다. 그 외인 경우는 전에 다루었던 RGB 거리 문제에서 저장했던 방식과 동일하다. (하단 링크 참조) 주의할 점은 집이 3 개인 경우인데 그 전단계인 집이 2 개인 경우 r-r, g-g, b-b에 대해서 배제해야 한다는 것이다. 코드는 다음과 같다.

 

#include <iostream>

#define R 0
#define G 1
#define B 2

int dp[1001][9];
int rgb[1001][3];


int main()
{
    int N;
    std::cin >> N;

    for (int i = 1; i <= N; i++) 
    {
        int r, g, b;
        std::cin >> r >> g >> b;

        rgb[i][0] = r;
        rgb[i][1] = g;
        rgb[i][2] = b;
    }

    //Red start
    dp[2][0] = rgb[1][R] + rgb[2][R]; // not case
    dp[2][1] = rgb[1][R] + rgb[2][G];
    dp[2][2] = rgb[1][R] + rgb[2][B];
    
    //Green start
    dp[2][3] = rgb[1][G] + rgb[2][R];
    dp[2][4] = rgb[1][G] + rgb[2][G];//not case
    dp[2][5] = rgb[1][G] + rgb[2][B];

    //Blue start
    dp[2][6] = rgb[1][B] + rgb[2][R];
    dp[2][7] = rgb[1][B] + rgb[2][G];
    dp[2][8] = rgb[1][B] + rgb[2][B];//not case

    if (N > 2) 
    {
        for (int i = 3; i <= N; i++) 
        {
            if (i == 3) 
            {
                dp[i][0] = dp[i-1][1] > dp[i-1][2] ? dp[i - 1][2] + rgb[i][R] : dp[i - 1][1] + rgb[i][R];
                dp[i][1] = dp[i-1][2] + rgb[i][G];
                dp[i][2] = dp[i-1][1] + rgb[i][B];

                dp[i][3] = dp[i - 1][5] + rgb[i][R];
                dp[i][4] = dp[i - 1][3] > dp[i-1][5] ? dp[i - 1][5] + rgb[i][G] : dp[i - 1][3] + rgb[i][G];
                dp[i][5] = dp[i - 1][3] + rgb[i][B];

                dp[i][6] = dp[i-1][7] + rgb[i][R];
                dp[i][7] = dp[i - 1][6] + rgb[i][G];
                dp[i][8] = dp[i-1][6] > dp[i - 1][7] ? dp[i - 1][7] + rgb[i][B] : dp[i - 1][6] + rgb[i][B];
            }
            else 
            {
                dp[i][0] = dp[i - 1][1] > dp[i-1][2] ? dp[i - 1][2] + rgb[i][R] : dp[i - 1][1] + rgb[i][R];
                dp[i][1] = dp[i - 1][0] > dp[i - 1][2] ? dp[i - 1][2] + rgb[i][G] : dp[i - 1][0] + rgb[i][G];
                dp[i][2] = dp[i - 1][1] > dp[i - 1][0] ? dp[i - 1][0] + rgb[i][B] : dp[i - 1][1] + rgb[i][B];

                dp[i][3] = dp[i - 1][4] > dp[i - 1][5] ? dp[i - 1][5] + rgb[i][R] : dp[i - 1][4] + rgb[i][R];
                dp[i][4] = dp[i - 1][3] > dp[i - 1][5] ? dp[i - 1][5] + rgb[i][G] : dp[i - 1][3] + rgb[i][G];
                dp[i][5] = dp[i - 1][3] > dp[i - 1][4] ? dp[i - 1][4] + rgb[i][B] : dp[i - 1][3] + rgb[i][B];

                dp[i][6] = dp[i - 1][7] > dp[i - 1][8] ? dp[i - 1][8] + rgb[i][R] : dp[i - 1][7] + rgb[i][R];
                dp[i][7] = dp[i - 1][6] > dp[i - 1][8] ? dp[i - 1][8] + rgb[i][G] : dp[i - 1][6] + rgb[i][G];
                dp[i][8] = dp[i - 1][6] > dp[i - 1][7] ? dp[i - 1][7] + rgb[i][B] : dp[i - 1][6] + rgb[i][B];
            }
        }
    }

    dp[N][0] = -1;
    dp[N][4] = -1;
    dp[N][8] = -1;

    int min = dp[N][1];

    for (int i = 2; i < 9; i++) 
    {
        if (dp[N][i] > 0 && min > dp[N][i]) 
        {
            min = dp[N][i];
        }
    }

    std::cout << min;

    return 0;
}

 

 이 것으로 글을 마친다.

 

https://messy-developing-diary.tistory.com/93

백준 1149, RGB 거리