백준 No.1149 [RGB거리]

// Baekjoon Online Judge No.1149 [RGB거리]

---

   Code   

#include <iostream>
 
using namespace std;
 
int N;
int price[1001][4];
int minSum[1001][4];
 
int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 3; j++) {
            cin >> price[i][j];
        }
    }
 
    minSum[1][1] = price[1][1];
    minSum[1][2] = price[1][2];
    minSum[1][3] = price[1][3];
 
    for (int i = 2; i <= N; i++) {
        minSum[i][1] += price[i][1] + min(minSum[i - 1][2], minSum[i - 1][3]);
        minSum[i][2] += price[i][2] + min(minSum[i - 1][1], minSum[i - 1][3]);
        minSum[i][3] += price[i][3] + min(minSum[i - 1][1], minSum[i - 1][2]);
    }
 
    int answer = 0;
    answer = min(minSum[N][1], min(minSum[N][2], minSum[N][3]));
    cout << answer;
}

---

   How to solve   

  <Dynamic Programming (동적 계획)>을 이용하여 문제를 풀어야하기 때문에 생각을 좀 하여야 했다. 결국 마지막엔 좀 복잡한 형태를 가질줄 알았는데 생각보다 간단하게 풀 수 있는 문제였다.

 

 

   int price[1001][4];  변수는 k번째 집에 RGB색중 하나를 칠할때 필요한 가격이다. 코드상에서 보면 처음에 입력을 받는것을 알 수 있다. 코드를 풀면서 빨간색은 1, 초록색은 2, 파란색은 3으로 두고 풀었다.

 

• price[k][1] : k번째 집에 빨간색을 칠할때 필요한 가격 ( 1 <= k <= N )
• price[k][2] : k번째 집에 초록색을 칠할때 필요한 가격 ( 1 <= k <= N )
• price[k][3] : k번째 집에 파란색을 칠할때 필요한 가격 ( 1 <= k <= N )

 

   int minSum[1001][4];  변수는 k번째 집에 RGB색중 하나를 칠할때 그때까지 쓰여지는 가격의 합의 최솟값이다.

  

• minSum[k][1] : k번째 집에 빨간색을 칠할때 그때까지 쌓인 최소 가격 ( 1 <= k <= N )
• minSum[k][2] : k번째 집에 초록색을 칠할때 그때까지 쌓인 최소 가격 ( 1 <= k <= N )
• minSum[k][3] : k번째 집에 파란색을 칠할때 그때까지 쌓인 최소 가격 ( 1 <= k <= N )

 

  코드 10번부터 15번 line까지는 price[i][j]에 가격을 입력하는 과정이다. 또한 17번 ~ 19번 line에서는 minSum[1][a]의 값을 price[1][a]값으로 초기화 해주었다. 이제 중요한것은 21번 ~ 25번 line이다.

 

  예를 들어서, 10번째 집에 빨간색을 칠해야하는 경우에 해당하는 값인 minSum[10][1]값을 생각해보자. 그러면 이 상황에선, 문제의 규칙에 따라 바로 이전집인 9번째 집은 빨간색이 아닌 초록색과 파란색중 하나이다. 그렇다면 우리는 minSum[10][1]값을 정하기 위해선 이전집이 초록색일 경우와 파란색일 경우를 생각해볼 수 있다.

 

• 9번째 집이 초록색인 경우 : minSum[10][1] = price[10][1] + minSum[9][2]
• 9번째 집이 파란색인 경우 : minSum[10][1] = price[10][1] + minSum[9][3]

  하지만, 우리는 저 두 경우 모두를 고려할 필요가 없다. 우리는 결국 제일 최소한의 가격을 얻어내야하기 때문에 minSum[10][1]에 price[10][1]의 값을 더한 뒤, 9번째 집이 초록색인 경우의 가격과 파란색인 경우의 가격중 더 가격이 적게 나가는 색을 칠하면 될 것 이다. 결국 아래와 같은 코드를 생각해볼 수 있다.

 

minSum[10][1] = price[10][1] + min( minSum[9][2], minSum[9][3] );

  이를 이제 일반화한 후 3가지 색을 다 고려하는 식을 생각해보면 아래와 같다.

 

minSum[k][1] = price[k][1] + min( minSum[k - 1][2], minSum[k - 1][3] ); minSum[k][2] = price[k][2] + min( minSum[k - 1][1], minSum[k - 1][3] ); minSum[k][3] = price[k][3] + min( minSum[k - 1][1], minSum[k - 1][2] ); 단, k는 2 이상의 정수.

  이제 위에서 구해진 점화식을 for문을 사용하여 2번째 집부터 N번째 집까지의 minSum값을 구할 수 있을 것이다. 그에 해당하는 부분이 코드 21번 ~ 25번 line이다. 위 설명에선 변수 이름을 k로 두었으나 아래 코드에선 i로 두었다는 점만 좀 고려하면 될 것 같다.

 

  마지막으로 정답을 프린트할땐 27번 ~ 29번 line처럼 minSum[N][1], minSum[N][2] 그리고 minSum[N][3]의 값중 제일 작은 값을 프린트하면 된다.