[BOJ 1149] (DP) RGB 거리 (C++)

RGB 거리 (Silver 1)

문제

전체 문제 보기

1149번: RGB거리

접근법

이 문제에서 구해야 하는 값은 총 N개의 집들이 각각 R, G, B 색상으로 칠하는데 필요한 비용이 주어질 때 모든 집을 칠하기 위한 최소의 비용을 구해야 한다. 집을 칠하기 위한 규칙은 옆집과 다른 색이기만 하면 된다. 아래와 같이 같은 색이 연속해서 나오지 않은 경우 모두 가능하다.

• RGRBRGRBRGRBRBRG
• RGBRGBRGRBGBRBGR

즉 N번 째 집을 칠할 수 있는 모든 경우의 수는 다음과 같다.

• N번째 집을 R로 칠하는 경우: N-1은 반드시 G 혹은 B 이다.
• N번째 집을 G로 칠하는 경우: N-1은 반드시 R 혹은 B 이다.
• N번째 집을 B로 칠하는 경우: N-1은 반드시 R 혹은 G 이다.

그런데 우리는 최솟값이 필요하다. 따라서 아래의 3가지 경우 중에서 최소 값이 정답이 된다.

• N번째 집을 R로 칠하는 경우: N-1이 G 인 경우와 B 인 경우 중 작은 값
• N번째 집을 G로 칠하는 경우: N-1이 R 인 경우와 B 인 경우 중 작은 값
• N번째 집을 B로 칠하는 경우: N-1이 R 인 경우와 G 인 경우 중 작은 값

전체 소스 코드

#include <iostream>
#include <array>
#include <algorithm>

#define endl '\n'
using namespace std;

const int MAX = 1'001;

enum Color : uint8_t
{
    R, G, B, Color_MAX
};

int main() {

    array<array<int, 3>, MAX> cache{};
    array<array<int, 3>, MAX> cost{};


    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N;  // 집의 수 2 <= N <= 1'000
    cin >> N;

    for (int i = 1; i <= N; ++i)
    {
        cin >> cost[i][R] >> cost[i][G] >> cost[i][B];
    }

    for (int i = 1; i <= N; ++i)
    {
        cache[i][R] = min(cache[i - 1][G], cache[i - 1][B]) + cost[i][R];
        cache[i][G] = min(cache[i - 1][R], cache[i - 1][B]) + cost[i][G];
        cache[i][B] = min(cache[i - 1][R], cache[i - 1][G]) + cost[i][B];
    }

    int answer = min({ cache[N][R], cache[N][G], cache[N][B] });

    cout << answer;

    return 0;
};

성능 평가

이 풀이의 시간 복잡도를 살펴보자. cache 배열에 1번 집부터 N번 집까지 가능한 RGB의 모든 경우를 계산하고 있다. 때문에 시간 복잡도는 \(O(N)\)이다. 그리고 공간 복잡도는 1번 집부터 N번 집까지 가능한 경우를 배열에 저장하기 때문에 마찬가지로 \(O(N)\)이다.

 

그런데 이 문제의 경우 공간 복잡도를 \(O(1)\)까지 최적화할 수도 있다. 공간 복잡도가 \(O(n)\)인 이유는 입력을 1부터 N까지 저장하는 cost 배열과 1부터 N까지 칠할 수 있는 모든 경우를 저장하는 cache 배열 때문이다. 하지만 이 문제에서는 입력된 n번째 cost 값은 n번째 집을 계산할 때 한번 사용되고, n번째 집까지 계산한 cache 값도 다음 집을 계산할 때 딱 한번 사용된다. 때문에 굳이 배열에 저장해 두고 프로그램이 종료될 때까지 저장하고 있을 필요가 없다. 아래와 같이 모든 경우의 수를 배열에 저장하지 않고 입력받은 값은 바로 사용하고, 계산된 값은 이전 집의 값만 저장하면 공간 복잡도를 \(O(1)\)까지 줄일 수 있다.

최적화 코드

#include <iostream>
#include <array>
#include <algorithm>

#define endl '\n'
using namespace std;

enum Color : uint8_t
{
    R, G, B, Color_MAX
};

int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N;  // 집의 수 2 <= N <= 1'000
    cin >> N;

    array<int, Color_MAX> cost{};
    array<int, Color_MAX> cache{};

    for (int i = 1; i <= N; ++i)
    {
        array<int, Color_MAX> Temp{};

        cin >> cost[R] >> cost[G] >> cost[B];

        Temp[R] = min(cache[G], cache[B]) + cost[R];
        Temp[G] = min(cache[R], cache[B]) + cost[G];
        Temp[B] = min(cache[R], cache[G]) + cost[B];

        cache[R] = Temp[R];
        cache[G] = Temp[G];
        cache[B] = Temp[B];
    }

    int answer = min({ cache[R], cache[G], cache[B] });

    cout << answer;

    return 0;
};