JArchive 프로그래밍 일기

문제

RGB거리 백준 1149번

리뷰

최소값을 구하는 문제이므로 DP로 문제를 풀었다. (최소, 최대, 경우의 수는 DP로 푼다)

이 문제는 '직전 값'과는 다른 색깔을 선택해야 한다는 것이 핵심이었다.

그래서 직전에 어떤 색을 칠했는지를 고려해서 현재 무슨 색을 선택할지 결정한다.

ex) 1을 칠했다면, 다음에는 2또는 3 중에서만 최소값을 골라야 한다.

역으로 생각하면, 현재 2를 칠한다면, 직전에는 1또는 3을 택했어야 한다.

배열 A에는 1행에서 R,G,B 값을 저장했다. 인덱스는 1,2,3 을 썼다.

배열 D에는 1행에서 마지막으로 R, G, B 값을 칠했을 경우의 최소값을 저장한다.

배열 A, D 둘다 0행이 아니라 1행부터 시작한다.

배열 D의 초기화는 배열 A의 1행의 값들로 초기화된다.

왜냐하면, 1번째 집에서 마지막으로 R값을 칠한 것의 최소값이 1번째 집의 R값이기 때문이다.

    // D 배열 인덱스도 1부터 시작. 
       D[1][1] = A[1][1];  // R을 마지막으로 칠한 경우. 
    D[1][2] = A[1][2];  // G를 마지막으로 칠한 경우. 
    D[1][3] = A[1][3];  // B를 마지막으로 칠한 경우. 

예를 들어, D[ 2 ] [ 2 ] 값을 구해보자.

D[ 2 ] [ 2 ] 는 2 번째 집을 G로 칠한 경우(2번째 색을 선택)의 최소값이다.

이것은 D[1] [1] 과 D[1] [3] 을 비교한 값에 A[2] [2] 를 더해서 구해진다.

1번째 집을 R값으로 칠한 경우의 최소값과 1번째 집을 B값으로 칠한 경우의 최소값 둘을 비교해서 최소값을 고른다. 그리고 현재 행 (2번째 집) A[2] [2 ] 값을 더한다.

따라서 점화식을 옮긴 코드는 아래와 같다.

      for(i = 2; i <= house; i++){ // 인덱스 2부터 시작

         D[i][1] = min(D[i-1][2], D[i-1][3]) + A[i][1]; // 현재 1를 택했다면, 직전에 2또는 3을 선택.
         D[i][2] = min(D[i-1][1], D[i-1][3]) + A[i][2]; // 현재 2를 택했다면, 직전에 1또는 3을 선택.
         D[i][3] = min(D[i-1][1], D[i-1][2]) + A[i][3]; // 현재 3을 택했다면, 직전에 1또는 2을 선택.
    }

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int A[1001][4];  // 3색 값 입력 받음  
int D[1001][4];

int main(void){

     int house, fir, se, th = 0;
     int i = 0;

    scanf("%d", &house);     

     for(i = 1; i <= house; i++){
         scanf("%d %d %d", &fir, &se, &th); 
         A[i][1] = fir;
         A[i][2] = se;
         A[i][3] = th;
    } // 입력받기 끝 

    // D 배열 인덱스도 1부터 시작. 
       D[1][1] = A[1][1];  // 1을 마지막으로 칠한 경우. 
    D[1][2] = A[1][2];  // 2를 마지막으로 칠한 경우. 
    D[1][3] = A[1][3];

      for(i = 2; i <= house; i++){ // 인덱스 2부터 시작

         D[i][1] = min(D[i-1][2], D[i-1][3]) + A[i][1]; // 현재 1를 택했다면, 직전에 2또는 3을 선택.
         D[i][2] = min(D[i-1][1], D[i-1][3]) + A[i][2]; // 현재 2를 택했다면, 직전에 1또는 3을 선택.
         D[i][3] = min(D[i-1][1], D[i-1][2]) + A[i][3]; // 현재 3을 택했다면, 직전에 1또는 2을 선택.
    }

    // 마지막 줄에는, 각각 마지막에 1또는 2또는 3을 칠한 경우의 최소값들이 들어있다.
    printf("%d", min( min(D[house][1], D[house][2]), D[house][3] )); 

    return 0;
}