[백준]1149-RGB거리(Dynamic Programming)

백준에서 단계별로 풀기를 위에서부터 100 문제 정도 풀면 동적 계획법이 나온다.

동적 계획법1 파트에서 4번까지는 피보나치 같은 비교적 간단한 문제만 나온다. 여기까지는 알고리즘에 대한 공부를 따로 하지 않아도 직관으로 어느 정도 풀 수준이라고 할 법하다고 생각한다.

 

하지만 이 문제는 대중적? 알고리즘의 한 부분인 Dynamic Programming을 공부하지 않으면 꽤나 고전할 법한 문제이다.

물론 따로 공부하지 않았다고 해서 풀지 못할 문제라는건 아니지만..

 

여하튼 이 문제는 동적 계획법을 처음 공부한 사람이 익숙해지기 위해 풀어보는 입문용 문제라고 봐도 좋을 것 같다.

 

자 이제 문제를 살펴보자.

i번째 집은 i-1번째와 i+1번째 집과 같은 색으로 칠할 수 없다.

1번째 집부터 차례대로 집의 색을 칠한다고 했을 때, 1번째 집은 아무 색을 칠하고, 2번째 집은 1번째 집의 색을 제외한 두 가지 색 중에서 하나를 선택해서 칠한다. 2번째 집을 칠할 때 3번째 집은 고려할 필요가 없다. 3번째 집을 칠할 때 2번째 집의 색을 고려하면 되기 때문이다. 첫 번째 집과 마지막 집은 이웃이 아니니, 이런 식으로 마지막 집까지 칠하면 색의 중복 문제는 해결된다.

 

자 그럼 진짜 문제는 최소비용이다.

p[i][color]를 i번째 집에 color라는 색을 칠할 때 최소비용이라고 정의하자. (위 문제에서 color는 r, g, b로 3가지이니 0, 1, 2로 할 수 있다.) 여기서 주의할 점은 "p[i]를 i번째 집까지 색을 칠할 때 최소비용이라고 정의할 거야!"라고 생각하면 안 된다는 것이다.

이게 무슨 말이냐면, 굳이 p[i][color]로 2차원 배열을 만든 이유가, p[i][0], p[i][1], p[i][2] 이 3가지 값을 모두 구한 다음에 이 중 최솟값을 반환하면 된다는 것이다.

 

자 그럼 p[i][color]는 어떻게 결정될까?

i번째 집에 color라는 색상을 칠한다는 것을 전제로 뒀으니, 문제에서 주어진 i번째 집에 color를 칠할 때의 비용은 당연히 포함된다.

그리고 여러 p[i - 1][exclude color] 값들 중 최솟값을 더하면 된다. 즉, p[i]에서 칠한 color라는 색을 제외한 나머지 색을 칠했을 경우의 i - 1번째 집까지의 최소비용들 중 최솟값을 고르면 된다는 것이다.

음.. 동적 계획법에 익숙하지 않으면 이 설명에 의아할 수 있는데, 나중에 동적 계획법에 대한 글을 따로 써야겠다. 모쪼록 위 설명만으로도 이해가 되었으면 좋겠다만..

 

여튼 p[i][color]를 구하는 방법은 이렇게 알았다. 간단하게 식으로 표현하면

p[i][color] = min(p[i - 1][colors exclude color];

라고 표현할 수 있다.

#include <iostream>
#include <cstdio>
using namespace std;
 
int RGB(int num, pair<int, int>** rgb);
 
int main() {
    int N;
    scanf("%d", &N);
    pair<int ,int>** pay = new pair<int, int>*[N];
    for (int i = 0; i < N; i++) {
        int r, g, b;
        scanf("%d %d %d", &r, &g, &b);
        pay[i] = new pair<int, int>[3];
        pay[i][0].first = r; pay[i][0].second = r;
        pay[i][1].first = g; pay[i][1].second = g;
        pay[i][2].first = b; pay[i][2].second = b;
    }
    printf("%d\n", RGB(N, pay));
}
 
int RGB(int num, pair<int, int>** rgb) {
    for (int i = 1; i < num; i++) {
        rgb[i][0].second += rgb[i - 1][1].second < rgb[i - 1][2].second ? rgb[i - 1][1].second : rgb[i - 1][2].second;
        rgb[i][1].second += rgb[i - 1][0].second < rgb[i - 1][2].second ? rgb[i - 1][0].second : rgb[i - 1][2].second;
        rgb[i][2].second += rgb[i - 1][0].second < rgb[i - 1][1].second ? rgb[i - 1][0].second : rgb[i - 1][1].second;
    }
    int min = rgb[num - 1][0].second;
 
    if (min > rgb[num - 1][1].second)
        min = rgb[num - 1][1].second;
    if (min > rgb[num - 1][2].second)
        min = rgb[num - 1][2].second;
 
    return min;
}

이게 내가 짠 코드다.

본래 정석?은 같은 크기의 배열을 하나 더 만드는 것이지만, 귀찮아서리.. pair<int, int>로 짰다.