[c++] BOJ 1149번 :: RGB거리

RGB 거리

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	42269	19789	14882	47.682%

문제

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보다 작거나 같은 자연수이다.

출력

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

알고리즘 분류

• 다이나믹 프로그래밍

나의 답

생각의 흐름

1. 완전탐색이 가능한가?

   2^(N) => 2^(1000)의 시간이 걸리기 때문에 불가능하다.

   심지어 시간제한이 0.5초이다.

2. 각 단계별로 생각 가능한가? (최적 부분 구조인가?)

   한 단계가 다음 단계들에 영향을 미친다.

   심지어 어디까지 영향을 미친다는 것 없이 이후의 모든 단계에 영향을 미친다.

ex_)

집1	집2	집3	집4
1	9	100	1000
2	8	101	1001
3	1	7	1

 이렇게 입력이 들어왔을 때, 집1과 집2로만 보면 더해서 가장 작은 수가 나오는 (1,1)을 택해야할 것이다. 하지만 집3까지 보면 (1,8,7)이 가장 작은 수의 집합이다. 따라서 집1의 선택은 집3의 선택과 독립적이지 않다.

이어서 집4까지 보았을 때는 (1,1,100,1)으로 바뀐다. 결국 특정한 index까지의 최적의 답이 이후의 최적의 답을 확신시킬 순 없다.

 그렇다면 완전탐색은 너무 오래걸리고, 단계 별로 쪼개서 볼 수도 없는데 어떻게 해야할까?

어쨌든 한 단계의 선택이 모든 단계에 영향을 미치는 거라면 집1부터 집N까지 RGB중 하나를 택하는 모든 경우의 수를 생각해야할 것이다. 하지만 완전탐색을 하되 시간을 줄이는 방법을 찾아보자.

이럴 때는 대부분 시간을 얻기위해 공간을 좀 사용하면 된다.

우선 완전 탐색일 때의 선택을 트리로 나타내보면 다음과 같다.

 집1의 선택을 우선 1로 고정시켰을 때 이러한 트리가 줄지어서 나온다. 트리는 집의 갯수 N만큼 아래로 뻗어 높이가 N이 될 것이며, 높이가 1씩 더해질 때마다 노드의 갯수는 2배로 증가하게 될 것이다. 이런 트리를 binary tree라고 한다.

완전탐색은 이와같이 binary tree가 나오게 되는데, 집1의 선택은 3가지가 가능하므로 전체 경우의 수는 3*2^(N)-1이다. 따라서 시간 내에 코드를 실행하기 어렵다.

 다만 위의 그림에서 집3의 선택이 1로 겹치는 걸 볼 수 있다. 그렇다면 이를 묶어서 다음과 같이 표현할 수 있다.

 

 이렇게 겹친 부분의 계산은 한번만 하는 식으로 구현하는 것이 다이나믹 프로그래밍이다.

즉, 이 문제는 다이나믹 프로그래밍이지만 최적부분구조를 가지고 있지는 않은 문제이다.

다이나믹 프로그래밍은 이 값이 이미 계산되었음을 어떻게 알 수 있을까? 를 고민해야하는데, 본인은 그냥 메모리를 쓰고 vector로 저만큼의 배열을 만들기로 했다.

 본인은 memorize하는 함수를 따로 쓰면서 다이나믹 프로그래밍을 전개하지 않고 애초에 묶인 트리의 구조로 자료구조를 만들었다.

 각 단계마다 1씩 노드의 수가 늘어나고 1부터 N까지의 집이 있으므로 N(N-1)/2 만큼의 저장공간이 필요하다. N의 최대는 1,000이므로 N^2이라고 해도 10^6이니 int 형(4byte)를 저장할 때 4*10^6byte = 4MB 정도 사용된다.

예제

 

위에서 소개한 예제에서 집1의 선택을 3으로 고정했을 때를 살펴보자. 다음과 같은 트리가 만들어진다.

 

맨 아래 노드부터 올라오면서 두 개의 값 중 작은 값을 위의 노드 값에 더해준다. 이를 반복하면

 

이런 트리가 나오는데, 맨 위의 노드값 112가 집1의 값이 3일 때 나올 수 있는 최소의 값이다.

이런 식으로 집1의 값이 1일 때, 2일 때 모두 진행한 후 3가지 값 중 가장 작은 값을 출력하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int RGB[1000][3];
int N;

int calMin(int first_num) {

    vector<int> arr[1000];
    for (int i = N-1; i >= 0; i--) {
        int plus_num = first_num;
        int j = i+1;
        while (j--) {
            int index = (plus_num++ + i) % 3;
            arr[i].push_back(RGB[i][index]);
        }
        first_num = (first_num+2)%3+1;
    }

    vector<int> result[1000];
    vector<int>::iterator iter;
    for (int i = N-1; i >= 1; i--) {
        for (int j = 0; j < arr[i].size()-1; j++) {
            arr[i - 1][j] += min(arr[i][j], arr[i][j+1]);
        }
    }
    return arr[0][0];
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> RGB[i][j];
        }
    }

    int result=1e9;
    for (int i = 0; i <= 2; i++) {
        result = min(result, calMin(i));
    }

    cout << result;
}

테스트케이스

4
1 2 3
9 8 1
100 101 7
1000 1001 1

103

4
1 2 3
100 101 7
9 8 1
1000 1001 1

17

다른 답

이렇게 복잡하게 할 필요 없이 한 집씩 받아오면서 6번씩만 계산하면 되는 문제였다. 집1의 RGB를 받아오고 집2의 RGB를 받아올 때,

집2 R => 집1 G or 집1 B
집2 G => 집1 R or 집1 B
집3 B => 집1 R or 집1 G

이렇게 6번만 계산해서 각 경우에 최소값을 저장하고 계속 진행하면 된다.

이는 위에 표시한 트리 모양을 거꾸로 올라가는 것이다.