BOJ1149

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

출력

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

나의 첫번째 답

처음 생각한 알고리즘을 코드로 구현했지만, 이는 정답이 아니었다.

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

std::vector<int> chooseColor(std::vector<int> colors, const int prevColor)
{
    std::vector<int> tempVec = colors;
    std::sort(tempVec.begin(), tempVec.end());

    int index = 0;

    if(prevColor == -1) index = 0;
    else if(prevColor == std::find(colors.begin(), colors.end(), tempVec[index]) - colors.begin())
        index = 1;

    std::vector<int> ret;
    ret.push_back(tempVec[index]);
    ret.push_back(std::find(colors.begin(), colors.end(), tempVec[index]) - colors.begin());    // 이번에 고른 인덱스

    return ret;
}

int getLeastFee(std::vector<std::vector<int>> fee)
{
    int totalFee = 0;
    int prevColor[fee.size() + 1] = {-1};     // 이전에 선택한 색을 저장할 배열

    for (size_t i = 0; i < fee.size(); i++)
    {
        std::vector<int> vec = chooseColor(fee[i], prevColor[i]);
        totalFee += vec[0];
        prevColor[i+1] = vec[1];
    }
    
    return totalFee;
}

int main() {

    int numOfhouses;
    int colors = 3;
    std::cin >> numOfhouses;
    std::vector<std::vector<int>> fee(numOfhouses, std::vector<int>(colors));


    for (size_t i = 0; i < numOfhouses; i++)
    {
        for (size_t j = 0; j < colors; j++)
        {
            std::cin >> fee[i][j];
        }
    }

    std::cout << getLeastFee(fee) << std::endl;
}

처음 생각한 아이디어는 다음과 같았다.

각 집들은 인접한 집과 다른 색이어야하기에, 집의 색을 고를 때 직전의 집과는 무조건 다른 색을 고르도록 했고, 너무도 당연하게 Greedy한 방식으로 풀었다.

그리고 이게 원인이었다.

매 순간 순간 최적을 선택했다고해서, 그 전체가 최적이라는 것을 보장하지 않는데, 이를 간과했다.

그래서 다시 생각했다. 전체가 최적인 경우의 수를 찾으려면 어떻게 해야 하는가.

가능한 모든 경우의 수를 진행하면 되지 않을까?

입력받은 비용(N행, 3열)을 순회하면서,

매 순간마다 고를 수 있는 모든 경우에 대해, 누적된 비용을 저장하는 배열을 만든다.

그리고 이 누적 비용은, (직전의 집에서 선택 가능한 색에 대한 비용의 최솟값) + (이번에 고른 색의 비용) 이렇게 정해질 것이다.

이해를 돕기위해 예를 들자면, 두번째 집의 색을 고를때는 첫번째 집에서 선택가능한 색의 경우가 있을 것이다.

만약에 이번에 Red를 골랐다면, 첫번째 집에서는 Green 혹은 Blue만 가능할 것이다.

그러면 [두번째집][Red]에 대한 누적 비용은, (첫번째 집에서 Green, Blue 중 더 적은 비용) + (이번에 Red를 칠하는 비용)이 된다.

그렇게 두번째 집에서 Red, Green, Blue에 대한 비용을 모두 계산하고 나면, 세번째 집에 대한 누적 비용을 계산할 때는 두번째 집을 참고해서 정할 것이다.

그렇게 이를 끝까지 반복하면 이 배열의 마지막 행에는 마지막 집을 각각의 색으로 칠했을 때의 최소 비용이 저장될 것이다.

두번째 답

위에서 설명한 방식을 코드로 구현하였고, 이는 정답이다.

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

int main() {

    int numOfhouses;
    int colors = 3;
    std::cin >> numOfhouses;
    std::vector<std::vector<int>> fee(numOfhouses, std::vector<int>(colors));


    for (int i = 0; i < numOfhouses; i++)
    {
        for (int j = 0; j < colors; j++)
        {
            std::cin >> fee[i][j];
        }
    }

    // 누적된 비용을 저장할 2차원 vector
    std::vector<std::vector<int>> AccumulatedFee(numOfhouses, std::vector<int>(colors));

    // 첫번째 집에 대해서는 3가지 색에 대한 비용을 모두 저장
    for (int i = 0; i < colors; i++)
    {
        AccumulatedFee[0][i] = fee[0][i];
    }
    
    // 두번째 집부터는 이전에 고른 누적 비용을 참고해서 계산
    for (int i = 1; i < numOfhouses; i++)
    {
        AccumulatedFee[i][0] = fee[i][0] + std::min(AccumulatedFee[i-1][1], AccumulatedFee[i-1][2]);
        AccumulatedFee[i][1] = fee[i][1] + std::min(AccumulatedFee[i-1][0], AccumulatedFee[i-1][2]);
        AccumulatedFee[i][2] = fee[i][2] + std::min(AccumulatedFee[i-1][0], AccumulatedFee[i-1][1]);
    }
    
    // 배열의 마지막 행에는 마지막 집을 각각의 색으로 칠했을 때의 최소 비용.
    // 이 중 최소를 구하면, 그것이 문제가 원하는 답일 것이다.
    int leastFee = std::min({AccumulatedFee[numOfhouses - 1][0], AccumulatedFee[numOfhouses - 1][1], AccumulatedFee[numOfhouses - 1][2]});

    std::cout << leastFee << std::endl;
}