[BOJ-1149][C++] RGB거리

문제

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 

3
26 40 83
49 60 57
13 89 99

 

예제 출력 1 

96

 

예제 입력 2 

3
1 100 100
100 1 100
100 100 1

 

예제 출력 2 

3

 

예제 입력 3 

3
1 100 100
100 100 100
1 100 100

 

예제 출력 3

102

 

예제 입력 4

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

 

예제 출력 4 

208

 

예제 입력 5

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

 

예제 출력 5

253

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 출처

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

1149번: RGB거리

 

---

 

문제 해결 방법

• 다음과 같이 @N@ 개의 줄을 갖는 2차원 배열에서 각 줄에서 가중치 하나를 선택해서 가중치 합의 최솟값을 출력하는 문제이다. (단, N+1번째 줄에서 숫자를 선택할 경우, N번째 줄에서 선택한 수의 위치에 있는 수를 선택해서는 안된다.)

26	40	83
49	60	57
13	89	99

• 처음에는 다음과 같이 (복잡하게) 첫번째 줄에서 0번째, 1번째, 2번째 위치에 있는 수를 선택한 후, 그 다음줄부터 최솟값을 찾아가는 방식으로 문제를 해결하려고 하였으나, 이 방법으로는 예제 입력 5의 결과가 제대로 출력되지 않는 문제점이 있었다. (253이 출력되어야 하나 310이 출력되었다. 그러나 예제 입력 1 ~ 4의 출력은 정상적으로 되었다.)

int Update(int n, int cnt) {
    int result, minNum, sum, idx;

    sum = 0;
    minNum = rgb[0][cnt];
    vIdx.push_back(cnt);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            if (vIdx.back() != j) {
                if (minNum > rgb[i][j]) {
                    minNum = rgb[i][j];
                    idx = j;
                }
            }
        }
        vIdx.push_back(idx);
        sum += minNum;
    }
    return sum;
}

int Calc(int n) {
    int result;

    for (int i = 0; i < 3; i++) {
        dp.push_back(Update(n, i));
    }

    // 최솟값 찾기
    result = 1002;
    for (auto i : dp) {
        if (result > i) {
            result = i;
        }
    }

    return result;
}

 

• 그래서 새로운 방법을 생각해야 했고, 보다 더 직관적이고 쉽게 이 문제를 해결할 수 있음을 알게 되었다.
• 다음과 같이 위치별로(@0@, @1@, @2@) 문제의 조건에 맞는 최솟값의 가중치들의 합을 누적해 나가면서, 누적한 값들의 최솟값을 출력하도록 하면 되는 것이다.

int Calc(int n) {
    int result;
    
    // 문제의 조건에 맞는 최솟값의 가중치들의 합을 누적해나간다.
    for (int i = 1; i <= n; i++) {
        rgb[i][0] += min(rgb[i - 1][1], rgb[i - 1][2]);
        rgb[i][1] += min(rgb[i - 1][0], rgb[i - 1][2]);
        rgb[i][2] += min(rgb[i - 1][0], rgb[i - 1][1]);
    }

    // 최솟값 구하기
    result = min(rgb[n][0], (rgb[n][1], rgb[n][2]));

    return result;
}

• 참고로, 이 문제의 해결 방법과 같이 이전 상태의 값을 어디에 넣어 놓고 활용하는 것은 전부 DP라고 한다.

 

코드

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

int N;
int rgb[1002][3];

void Input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> rgb[i][j];
        }
    }
}

int Calc(int n) {
    int result;
    
    // 문제의 조건에 맞는 최솟값의 가중치들의 합을 누적해나간다.
    for (int i = 1; i <= n; i++) {
        rgb[i][0] += min(rgb[i - 1][1], rgb[i - 1][2]);
        rgb[i][1] += min(rgb[i - 1][0], rgb[i - 1][2]);
        rgb[i][2] += min(rgb[i - 1][0], rgb[i - 1][1]);
    }

    // 최솟값 구하기
    result = min(rgb[n][0], (rgb[n][1], rgb[n][2]));

    return result;
}

void Output() {
    cout << Calc(N) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Output();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [동적 계획법 1]
• 실버I