[C언어] 백준 | 17404번 RGB거리 2

문제 링크

평범한 rgb거리 문제에서 첫 번째 집과 마지막 집이 같은 색이면 안 된다는 조건이 추가된 문제입니다.

 

그래서 예제 1번을 보시면 원래의 최솟값은 26  57 13을 선택했을 때의 96이지만,

1번 집과 3번 집의 색이 다른 40 57 13 을 골랐을 때의 110이 출력되는 모습을 볼 수 있습니다.

 

저는 간단하게 생각해서 살짝 코드가 더럽지만 아주 쉽게 풀었습니다!

바로 1번 집과 2번 집에는 같은 색이 불가능하다는 것을 이용했는데요.

위의 상황을 생각해보면, 1번 집에서 빨강을 골랐을 경우 2번 집의 빨강 비용을 100만으로 바꿔주고(이렇게 하면 2번 집이 빨강인 경우 최솟값이 될 수가 없습니다.)  초록, 파랑에는 1번 집의 빨강 비용을 더해준 후 일반적인 rgb거리 1번 문제를 풀듯이 풀었습니다.

마지막에 총 비용을 계산할 땐 n번째 집이 빨강인 경우를 제외하고 나머지 2가지 중 최솟값을 구해주면 되죠.

 

그래서 저는 dp1 dp2 dp3 배열 3가지를 준비해서

각각 1번 집이 빨강, 초록, 파랑인 경우의 총비용. 그러니까 3 * 2 = 6가지의 값 중 최솟값을 찾아서 출력시켰더니 정답을 받았습니다.

 

밑의 주석에 설명 달아놨습니다.

#include <stdio.h>
#define min(x, y) ((x) < (y) ? (x) : (y))

int main() {
    int arr[1002][3], n;
    int dp1[1002][3], dp2[1002][3], dp3[1002][3];
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 3; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    dp1[1][0] = 1000000; //1번 집이 빨강인 경우 2번 집 빨강 비용은 백만
    dp1[1][1] = arr[0][0] + arr[1][1];
    dp1[1][2] = arr[0][0] + arr[1][2];
    dp2[1][1] = 1000000; //1번 집이 초록인 경우 2번 집 초록 비용은 백만
    dp2[1][0] = arr[0][1] + arr[1][0];
    dp2[1][2] = arr[0][1] + arr[1][2];
    dp3[1][2] = 1000000; //1번 집이 파랑인 경우 2번 집 파랑 비용은 백만
    dp3[1][1] = arr[0][2] + arr[1][1];
    dp3[1][0] = arr[0][2] + arr[1][0];        
    for(int i = 2; i < n; i++) {
       dp1[i][0] = min(dp1[i - 1][1], dp1[i-1][2]) +arr[i][0];
       dp1[i][1] = min(dp1[i - 1][0], dp1[i-1][2]) +arr[i][1];
       dp1[i][2] = min(dp1[i - 1][0], dp1[i-1][1]) +arr[i][2];
       dp2[i][0] = min(dp2[i - 1][1], dp2[i-1][2]) +arr[i][0];
       dp2[i][1] = min(dp2[i - 1][0], dp2[i-1][2]) +arr[i][1];
       dp2[i][2] = min(dp2[i - 1][0], dp2[i-1][1]) +arr[i][2];
       dp3[i][2] = min(dp3[i - 1][0], dp3[i-1][1]) +arr[i][2];              
       dp3[i][0] = min(dp3[i - 1][1], dp3[i-1][2]) +arr[i][0];
       dp3[i][1] = min(dp3[i - 1][0], dp3[i-1][2]) +arr[i][1];
    }

    int a = min(dp1[n-1][1], dp1[n-1][2]); //1번 집이 빨강이니까 n번 집이 초록, 파랑인 경우만 생각
    int b = min(dp2[n-1][0], dp2[n-1][2]);
    int c = min(dp3[n-1][0], dp3[n-1][1]);
    printf("%d", a < b ? (a < c ? a : c) : (b < c ? b : c)); // a, b, c 중 최솟값 구하기
}