[백준 17404] RGB거리 2

 

 DP 문제이다. 직관적으로 떠오르는 DP 로직을 그대로 적용할 수 있다. 집에 칠한 색별로 비용을 나눠서 저장하고, 다음 집을 칠할 때 이것을 참고해서 겹치지 않는 색 구성으로 최소 비용을 도출하는데에 이용한다.

 만약 i번 집을 빨강으로 칠하려는 경우의 DP 테이블 값을 구하려 한다면, i-1번 집을 초록으로 칠한 최소 비용과 파랑으로 칠한 최소 비용 중 더 작은 값에 i번 집을 빨강으로 칠하는 비용을 더한 값이 될 것이다.

 

 하나 까다로운 조건이 있다면, 결국 집이 일종의 원순열 형태로 놓여져있다고 생각해야 한다는 점이다. N번 집을 칠할 때는 1번 집의 색을 고려해야 하는데, 위와 같은 DP 테이블의 경우 이전 집의 색은 알 수 있으나 1번 집에 대한 정보는 소실된 상태가 된다. 

 그래서 나는 애초부터 DP 테이블을 첫 집의 색 별로 총 3개를 생성했다. 그러니까 N*3(3개의 색)짜리 배열이 총 3개 있는 것이다. 이를 이용하면 각 테이블에서 N번 집과 1번 집의 색이 겹치지 않는 경우만 해 후보 집합에 넣고 비교할 수 있게 된다. 

 

 전체 시간 복잡도는 O(n)이 되고, 무난하게 통과할 수 있었다.

 

#include <iostream>
#include <algorithm>
#define INF_COST 987654321

using namespace std;

int startWithRed[1000][3]; // { red, green, blue }
int startWithGreen[1000][3];
int startWithBlue[1000][3];

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n >> startWithRed[0][0] >> startWithGreen[0][1] >> startWithBlue[0][2];
    startWithRed[0][1] = INF_COST;
    startWithRed[0][2] = INF_COST;
    startWithGreen[0][0] = INF_COST;
    startWithGreen[0][2] = INF_COST;
    startWithBlue[0][0] = INF_COST;
    startWithBlue[0][1] = INF_COST;

    int redCost, greenCost, blueCost;
    for(int i=1; i<n; i++) {
        cin >> redCost >> greenCost >> blueCost;

        startWithRed[i][0] = min(startWithRed[i-1][1], startWithRed[i-1][2]) + redCost;
        startWithRed[i][1] = min(startWithRed[i-1][0], startWithRed[i-1][2]) + greenCost;
        startWithRed[i][2] = min(startWithRed[i-1][0], startWithRed[i-1][1]) + blueCost;

        startWithGreen[i][0] = min(startWithGreen[i-1][1], startWithGreen[i-1][2]) + redCost;
        startWithGreen[i][1] = min(startWithGreen[i-1][0], startWithGreen[i-1][2]) + greenCost;
        startWithGreen[i][2] = min(startWithGreen[i-1][0], startWithGreen[i-1][1]) + blueCost;

        startWithBlue[i][0] = min(startWithBlue[i-1][1], startWithBlue[i-1][2]) + redCost;
        startWithBlue[i][1] = min(startWithBlue[i-1][0], startWithBlue[i-1][2]) + greenCost;
        startWithBlue[i][2] = min(startWithBlue[i-1][0], startWithBlue[i-1][1]) + blueCost;                
    }   

    int candidateList[6] = {
        startWithRed[n-1][1], startWithRed[n-1][2],
        startWithGreen[n-1][0], startWithGreen[n-1][2],
        startWithBlue[n-1][0], startWithBlue[n-1][1]
    };

    int result = *min_element(candidateList, candidateList+6);

    cout << result;
}