1149

백준 1149번

Link: 1149번: RGB 거리

---

문제 설명

마을의 집 갯수와 각 집을 빨강, 초록, 파랑으로 각각 칠하는데 드는 비용이 입력으로 주어졌을때 마을의 모든 집을 칠하는 최저 비용을 구하는 문제.

이웃하는 집들은 같은 색으로 칠할 수 없다는 조건도 붙었다.

작년에 답보고 풀었던 기억이 나는 문제. 이번에는 꼭 내 힘으로 풀어내리라 결심하고 풀어보았다.

우선 이웃하는 집들이 같은 색이 될수 없다는 조건을 단순화하여 앞집이랑만 다른 색이면 되지 않나? 라는 생각으로 풀었다.

틀리고 한참 고민하고서야 왜 틀렸는지 알게 되었다. 반드시 최저값만으로 구성된 조합이 존재하지 않는 경우가 있다는 것.

거꾸로도 풀어보고 어떻게든 풀어보려 애써봤는데 결국 안풀려서 예전 답을 보고 풀었다…

생각보다 매우 단순했는데, 처음 칠하는 비용을 0으로 초기화한 다음 모든 경우를 따져가며 답을 구하는 방식이었다.

예를 들면 DP[i][0]은 DP[i-1][1]과 DP[i-1][2] 중 작은 값에다가 칠하는 비용인 price[i][0]을 더하는 식.

즉 DP[i][0]은 i번째 집을 0번째 색으로 칠한다는 것을 의미한다. 당연히 앞집이랑은 색이 겹칠 일이 없다.

온갖 방법 다 생각해보다 답을 봤는데 정말 간단하게 풀려서 허무했다;;;

2시간정도 고민해봤지만 못풀겠어서 결국 포기했던 점이 아쉽지만, 이러저러한 방법을 최대한 시도해 본 점은 나름 만족스럽다.

다음에 푸는 문제들은 이런 고민끝에 끝까지 풀어낼 수 있길!!

---

내가 짰다가 틀린 코드

//
// Created by Keith_Lee on 02/01/2019.
//

#include <iostream>

using namespace std;

int N;

int main(){
    cin >> N;

    int price[N][3];
    int DP[N][2];

    for(int i=0; i<N; i++){
        cin >> price[i][0] >> price[i][1] >> price[i][2];
    }

    for(int i=0; i<N; i++){
        int min = 1001;

        if(i == 0){
            for(int j=0; j<3; j++){
                if(min > price[0][j]){
                    min = price[0][j];
                    DP[0][0] = min;
                    DP[0][1] = j;
                }
            }
        }
        else{
            for(int j=0; j<3; j++){
                if(j != DP[i-1][1]){
                    if(min + price[i][j] > DP[i-1][0] + price[i][j]){
                        min = price[i][j];
                        DP[i][0] = min + DP[i-1][0];
                        DP[i][1] = j;
                    }
                }
            }
        }
    }

    cout << DP[N-1][0] << '\n';

    return 0;
}

---

정답 코드

//
// Created by Keith_Lee on 02/01/2019.
//

#include <iostream>

using namespace std;

int N;

int min(int a, int b){
    return (a > b) ? b : a;
}

int main(){
    cin >> N;

    int price[N+1][3];
    int DP[N+1][3];

    for(int i=1; i<=N; i++){
        cin >> price[i][0] >> price[i][1] >> price[i][2];
    }

    price[0][0] = price[0][1] = price[0][2] = 0;
    DP[0][0] = DP[0][1] = DP[0][2] = 0;

    for(int i=1; i<N+1; i++){
        DP[i][0] = min(DP[i-1][1], DP[i-1][2]) + price[i][0];
        DP[i][1] = min(DP[i-1][0], DP[i-1][2]) + price[i][1];
        DP[i][2] = min(DP[i-1][0], DP[i-1][1]) + price[i][2];
    }

    cout << min(min(DP[N][0], DP[N][1]), DP[N][2]) << '\n';

    return 0;
}

---