[C++] 백준 BOJ 1149 RGB 거리

문제 링크 : https://boj.kr/1149

어떤 집을 R, G, B 중 하나로 색칠할 때 인접한 이웃 끼리는 서로 색이 겹치면 안된다.  

한 집을 R로 선택하게 되면 그 다음에 올 수 있는 이웃의 값은 G, B 중에 하나만 올 수 있게 된다.

그 중에 G를 선택했다면 그 다음 값은 R, B 중에 선택해야 한다.

R, G, B의 3가지 값 중에서 하나를 선택하면 그 값을 제외한 2가지를 선택할 수 있다.

2가지 선택값 중에서 하나를 선택하면 그 뒤에는 또 2가지를 선택할 수 있는 경우의 수가 주어진다.

이 과정을 반복하면 3*2*2*2* .....가지의 경우의 수가 나오며 일반항으로 고쳐보면 3*2^(N-1)가지의 경우를 계산해야 함을 알 수 있다.

이를 빅-오 표기법으로 바꿔보면 O(2^N)임을 알 수 있다. N이 증가될 때마다 2가지씩 계속 꼬리에 꼬리를 무는 형태로 나온다.

그렇기 때문에 이 문제는 반드시 동적 계획법으로 풀어야 한다.

이 그림을 보면 한가지 공통 규칙을 발견할 수 있다.

같은 색으로 칠해진 부분은 부모 노드로 자기 자신의 루트 노드를 제외한 나머지 2가지 경우 중 한가지를 갖는 것을 알 수 있다.

빨간색 공통 부분의 루트 노드인 B를 기준으로 보면 그 상위 단계에 올 수 있는 노드는 R과 G의 경우이다.

우리가 찾고자 하는 조건은 최소 값들의 합이기 때문에 두가지 케이스 중에서 가장 작은 값만 취할 수 있는 경우만 생각하여 계속 연산을 거듭하면 된다.

(그림이 헷갈린다면 색깔을 유심히 보도록 하자)

위 그림에서 공통되는 부분에서 루트노드만 남기고 나머지 부분을 제거한 그림으로 표현해보았다.

현재 노드의 상태를 구하기 위해선 각 단계당 6번의 비교만 하면 되는 것으로 줄어들게 되었다.

R, G, B의 3가지 수 중에 2가지를 고르는 경우가 3번이므로 2*3이 된다.

골라진 2가지의 부모 노드 중에서 작은 값 만을 취하고 자기자신과 더하여 저장한다.

그리고 이렇게 골라진 2단계 레벨의 R(초록), B(빨강), G(보라)의 3가지 색상은 하위 3단계 레벨에서도 마찬가지로 같은 연산이 수행된다.

경우의 수를 식으로 표현하면 (2*3) * (N-1)회의 연산으로 대폭 줄게 된 것이다.

DP를 사용하여 O(2^N)을 O(N)까지 줄이게 되었다.

이를 DP 식으로 표현하면 다음과 같다. N은 단계를 나타내고 C는 색깔을 나타낸다.

DP[N][R] = min(DP[N-1][G], DP[N-1][B]) + R

DP[N][G] = min(DP[N-1][R], DP[N-1][B]) + G

DP[N][B] = min(DP[N-1][R], DP[N-1][G]) + B

// BOJ 1149 RGB 거리
#include <bits/stdc++.h>
 
using namespace std;
 
int dp[1001][3];
 
int min(int a, int b){
    return a > b ? b: a;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num, r, g, b;
    cin >> num;
    for(int i = 1; i <= num; i++) {
        cin >> r >> g >> b;
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + r;
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + g;
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + b;
    }
    cout << min(dp[num][0], min(dp[num][1], dp[num][2]));
 
    return 0;
}