백준 17404번: RGP 거리 2

[문제 링크]

---

2차원 DP 문제였지만 3차원 DP로 풀어서 코드가 복잡해졌다.

N번째 집의 경우 1번째 집의 색깔과 겹치면 안되기 때문에 이 조건을 처리하기 위해 1차원 더 추가해서 첫번째 집에 어떤 색깔을 칠했는지 캐싱했는데, 2차원 배열로 선언한 뒤 첫번째 집을 R, G, B 각각 칠했을 경우에 대해 각각 DP 로직을 수행해서 그중 가장 비용이 작은 값을 구해도 된다. 2차원 배열로 선언하는 방식이 캐싱하는데 필요한 메모리를 절약할 수 있다.

---

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define INF 987654321
int memo[1000][3][3];

void bottomup(vector<vector<int>>& costs, int N)
{
    int R = 0;
    int G = 1;
    int B = 2;
    
    memo[0][R][R] = costs[0][R];
    memo[0][G][G] = costs[0][G];
    memo[0][B][B] = costs[0][B];
    
    for(int i=1; i<N; i++)
    {
        if(i + 1 == N)
        {
            memo[i][R][G] = min(memo[i-1][R][R], memo[i-1][R][B]) + costs[i][G];
            memo[i][R][B] = min(memo[i-1][R][R], memo[i-1][R][G]) + costs[i][B];

            memo[i][G][R] = min(memo[i-1][G][G], memo[i-1][G][B]) + costs[i][R];
            memo[i][G][B] = min(memo[i-1][G][R], memo[i-1][G][G]) + costs[i][B];

            memo[i][B][R] = min(memo[i-1][B][G], memo[i-1][B][B]) + costs[i][R];
            memo[i][B][G] = min(memo[i-1][B][R], memo[i-1][B][B]) + costs[i][G];
        }
        else 
        {
            memo[i][R][R] = min(memo[i-1][R][G], memo[i-1][R][B]) + costs[i][R];
            memo[i][R][G] = min(memo[i-1][R][R], memo[i-1][R][B]) + costs[i][G];
            memo[i][R][B] = min(memo[i-1][R][R], memo[i-1][R][G]) + costs[i][B];

            memo[i][G][R] = min(memo[i-1][G][G], memo[i-1][G][B]) + costs[i][R];
            memo[i][G][G] = min(memo[i-1][G][R], memo[i-1][G][B]) + costs[i][G];
            memo[i][G][B] = min(memo[i-1][G][R], memo[i-1][G][G]) + costs[i][B];
            
            memo[i][B][R] = min(memo[i-1][B][G], memo[i-1][B][B]) + costs[i][R];
            memo[i][B][G] = min(memo[i-1][B][R], memo[i-1][B][B]) + costs[i][G];
            memo[i][B][B] = min(memo[i-1][B][R], memo[i-1][B][G]) + costs[i][B];
        }
    }
    
    int result = INF;
    for(int first = R; first<=B; ++first)
    {
        for(int here = R; here<=B; ++here)
        {
            if(here==first) continue;
            result = min(result, memo[N-1][first][here]);
        }
    }
    
    cout << result;
}

int main(void)
{
    fill_n(memo[0][0], 1000*3*3, INF);
    
    int N;
    cin >> N;
    
    vector<vector<int>> costs(N, vector<int>(3));
    
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<3; ++j)
        {
            cin >> costs[i][j];
        }
    }
    
    bottomup(costs, N);
    
    return 0;
}