문제

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

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

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

입력

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

출력

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

접근 과정

최대 1000개의 집을 3가지 색으로 나눠 칠해야하는 문제이다. 칠할 수 있는 경우의 수를 따지면 \(3^1000\)가지로 이 모든 경우에 대한 비용을 따지자면 제한시간(0.5초)을 초과할 것이다.
최근 비슷한 유형의 문제를 많이 풀었더니 금방 DP를 활용한 풀이법이 떠올랐다. 완전 탐색을 수행하는 calcMinCost(house, color) 를 구현하였다. 해당 함수는 house번째 집을 color에 해당하는 색으로 칠했을 때 사용되는 최소 비용을 반환하는 함수이며, 이전 번호의 집을 칠했을 때 최소 비용을 계산하도록 재귀호출을 수행한다. 이 때 조건을 만족하기 위해 color와 색이 같은 경우는 재귀호출을 하지 않도록 하였다.
함수 호출의 결과를 캐시배열 minCost에 저장하여 한 번 계산을 수행한 경우의 수에 대해서는 즉각적으로 값을 반환하여 중복된 연산을 하지 않도록 하였다.
익숙한 만큼 금방 구현했지만 항상 DP 문제를 재귀로만 풀려 했던 것 같아 제출 후에 연습삼아서 반복문을 통한 하향식 접근법으로도 구현해보았다. 해보니 이쪽이 좀 더 간단한 것 같기도?

소스 코드

재귀를 이용한 풀이

#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

int colorCost[1001][3];
int minCost[1001][3];

int calcMinCost(int house, int color) {
    if (house == 0) { return 0; }
    if (color != -1 && minCost[house][color] != -1) {
        return minCost[house][color];
    }

    int result = 1e8;
    for (int prevColor = 0; prevColor < 3; ++prevColor) {
        if (color == prevColor) continue;
        result = min(result, calcMinCost(house - 1, prevColor) + colorCost[house][prevColor]);
    }

    minCost[house][color] = result;
    return result;
}

int main() {
    int N;
    memset(minCost, -1, sizeof(minCost));

    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> colorCost[i][0] >> colorCost[i][1] >> colorCost[i][2];
    }

    cout << calcMinCost(N, -1);
    return 0;
}

반복문을 이용한 풀이

#include <cmath>
#include <iostream>
using namespace std;

int minCost[1001][3];

int main() {
    int N;
    int colorCost[1001][3];
    
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> colorCost[i][0] >> colorCost[i][1] >> colorCost[i][2];
    }

    for (int i = 1; i <= N; ++i) {
        minCost[i][0] = min(minCost[i - 1][1], minCost[i - 1][2]) + colorCost[i][0];
        minCost[i][1] = min(minCost[i - 1][0], minCost[i - 1][2]) + colorCost[i][1];
        minCost[i][2] = min(minCost[i - 1][0], minCost[i - 1][1]) + colorCost[i][2];
    }

    cout << min(min(minCost[N][0], minCost[N][1]), minCost[N][2]);
    return 0;
}