[백준 17404번] RGB거리 2

문제 링크

https://www.acmicpc.net/problem/17404

 

문제 요약

N개의 집을 다음 두 개의 규칙에 맞게 빨강, 초록, 파랑 중 하나로 칠해야 한다.

1. 인접한 두 집의 색이 달라야 한다.
2. 1번 집과 N번 집의 색이 달라야 한다.

각 집을 특정 색으로 칠하는 비용이 주어졌을 때, 모든 집을 규칙에 맞게 칠할 때 드는 최소 비용을 구하는 문제이다.

원래 문제에는 규칙이 세 개 있지만, 이해를 돕기 위해 두 개로 정리했다.

 

문제 풀이

이 문제는 동적 계획법(dynamic programming)을 이용해 해결할 수 있다. 먼저, 부분 문제를 해결할 수 있는 함수를 정의한다.

 

\(findMinCost(idx, prevColor) =\) idx - 1번째 집을 prevColor로 칠했을 때, idx번째 집부터 마지막 집까지 규칙에 맞게 칠할 수 있는 최소 비용

 

이제 이 함수를 바탕으로 다음과 같은 점화식을 세울 수 있다.

 

\(findMinCost(idx, prevColor)\)

\(= \min_{\rm \text{color} \in \text{{R,G,B}} \setminus \text{{prevColor}}}\)\(findMinCost(idx + 1, color) + cost[idx][color]\)

 

이 점화식을 함수로 구현한 다음에 메모이제이션 기법을 이용해 문제를 풀 수 있다.

 

근데... 이러면 1번 집과 N번 집의 색이 달라야 한다는 조건을 고려하지 않은 거 아닌가요?

 

맞다. 이 점화식은 1번 집과 N번 집의 색이 달라야 한다는 조건을 만족하지 않는 점화식이다. 이를 해결하기 위해 약간의 꼼수가 필요하다.

 

먼저 1번 집의 색을 하나 결정한다. 그다음 마지막 집의 색을 고를 때 이전 집의 색뿐만 아니라 1번 집의 색도 고려할 수 있도록 점화식을 수정한다. 바꾼 점화식을 이용해 1번 집을 빨강, 초록, 파랑으로 각각 색칠한 경우에 대해 전체 집을 색칠하는 최소 비용을 계산하고, 그중 가장 작은 값을 선택한다. 이렇게 하면 기존 점화식의 큰 변화 없이 문제의 조건을 만족하면서 모든 집을 칠하는데 드는 최소 비용을 계산할 수 있다.

 

소스 코드

#include <stdio.h>
#include <algorithm>

using namespace std;

const int INF = 987654321;
int n, cost[1010][3], dp[1010][3];

void init() {
    for (int i = 0 ; i < n ; ++i) {
        for (int j = 0 ; j < 3 ; ++j) {
            dp[i][j] = INF;
        }
    }
}

int findMinCost(int pos, int prevColor, int firstColor) {
    if (pos == n) {
        return 0;
    }
    
    int& ret = dp[pos][prevColor];
    
    if (ret != INF) {
        return ret;
    }
    
    for (int currentColor = 0 ; currentColor < 3 ; ++currentColor) {
        if (currentColor == prevColor || (pos == n - 1 && currentColor == firstColor)) {
            continue;
        }
        
        ret = min(ret, findMinCost(pos + 1, currentColor, firstColor) + cost[pos][currentColor]);
    }
    
    return ret;
}

int main() {
    scanf("%d", &n);
    
    for (int i = 0 ; i < n ; ++i) {
        for (int j = 0 ; j < 3 ; ++j) {
            scanf("%d", &cost[i][j]);
        }
    }
    
    int ans = INF;
    
    for (int i = 0 ; i < 3 ; ++i) {
        init();
        ans = min(ans, findMinCost(1, i, i) + cost[0][i]);
    }
    
    printf("%d\n", ans);
}