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

 

1149번: RGB거리

알고리즘 스터디의 첫 문제이다. 이 문제의 알고리즘은 Dynamic Programming 이다.

이웃하는 집의 색이 같지 않게 하면서 모든 집을 칠해야하고, 이 때의 최소 비용을 구해야한다.

제일 처음 생각했던 건 Greedy 방식이다. 매순간 마다 최소 비용을 선택하되 이웃하는 집의 색이 같지 않게 칠하면 된다.

3
1 100 100
100 100 100
1 100 100

위와 같은 입력에서 입력이 1번 집은 최소 비용이 1인 빨강을 선택하고 2번집은 최소 비용이 100인 파랑, 초록중에 아무거나 선택하면 된다.  3번집은 다시 빨간색을 선택할수 있으므로 쉽게 해결할 것 같았다.

하지만 이 방식은 쉽게 막혔다. 다음 입력을 생각해보자.

3
1 100 100
100 10 100
100 1 100

이때의 최소 비용은 102가 나온다. 하지만 Greedy하게 조건의 맞는 최솟값을 찾으면 111이 나오게 된다.

 

그 다음은 Dynamic Programming을 사용한다. Dynamic Programming은 Memoization이라는 기법을 활용한다. 이전에 선택했던 값을 기억하면서 그 다음 선택에 영향을 줄수 있는 방법이기 때문에 이를 사용했다. 

Brute Force로 모든 선택을 저장하게 된다면 공간복잡도가 O(3^N)이 된다. 아무리 열심히 가지치기한다고 해도 메모리 초과가 뜰거같으니 생각하진 않았다. 

내가 적용한 방법은 모든 선택을 저장하는 건 맞지만 효율적으로 저장하는 것이었다. 이웃되는 집에 각각의 색깔을 칠한 비용을 저장하면 그다음 집도 각 색상을 칠할때 비용을 알수 있게 되고, 마지막 집의 최소 비용까지 알수 있게 된다. 뭔가 설명이 이해가 잘안될거같으니 코드를 보자.

#include <iostream>
#include <algorithm>
#include <array>
using namespace std;

array<array<int, 3>, 1000> arr, memo;

int main()
{
    // 1 Initialze
    int numHouse;
    cin >> numHouse;
    for (int i = 0; i < numHouse; i++)
    {
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }

    // 2 Calculate
    memo[0][0] = arr[0][0];
    memo[0][1] = arr[0][1];
    memo[0][2] = arr[0][2];
    for (int r = 1; r < numHouse; r++)
    {
        memo[r][0] = arr[r][0] + min(memo[r - 1][1], memo[r - 1][2]);
        memo[r][1] = arr[r][1] + min(memo[r - 1][0], memo[r - 1][2]);
        memo[r][2] = arr[r][2] + min(memo[r - 1][0], memo[r - 1][1]);
    }

    // 3 Print answer
    cout << *(min_element(memo[numHouse - 1].begin(), memo[numHouse-1].end())) << endl;
    return 0;
}

이런방식으로 현재 집의 칠하는 비용을 모두 저장하면 마지막 배열에 최소비용을 구할수 있다.

---

파이썬으로 풀었던 내용

[백준] 1149 RGB거리