[백준/C언어] 1149번 - RGB거리

백준 웹사이트 "1149번 - RGB거리" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1149번: RGB거리

---

소스 코드

#include <stdio.h>

int min(int a, int b);

int main(void){
    // color[n][i]: n+1번째 집을 i 색깔로 칠하는 비용 (i=0: 빨강, i=1: 초록, i=2: 파랑)
    // price[n][i]: n+1번째 집을 i 색깔로 칠할 때, 1~n까지 모든 집들을 칠하는 최소 비용
    // price[n+1][0] = min(price[n][1], price[n][2]) + color[n+1][0]
    // 최종 답: price[N-1][0], price[N-1][1], price[N-1][2]의 최솟값

    int N;
    scanf("%d", &N);

    int color[N][3];
    for(int i=0; i<N; i++){
        for(int j=0; j<3; j++){
            scanf("%d", &color[i][j]);
        }
    }

    int price[N][3];
    price[0][0] = color[0][0], price[0][1] = color[0][1], price[0][2] = color[0][2];
    //printf("price[0][0]: %d, price[0][1]: %d, price[0][2]: %d\n", price[0][0], price[0][1], price[0][2]);
    
    for(int i=1; i<N; i++){
        price[i][0] = min(price[i-1][1], price[i-1][2]) + color[i][0];
        price[i][1] = min(price[i-1][2], price[i-1][0]) + color[i][1];
        price[i][2] = min(price[i-1][0], price[i-1][1]) + color[i][2];
        //printf("price[%d][0]: %d, price[%d][1]: %d, price[%d][2]: %d\n", i, price[i][0], i, price[i][1], i, price[i][2]);
    }

    int result = min(min(price[N-1][0], price[N-1][1]), price[N-1][2]);
    printf("%d\n", result); 
}

int min(int a, int b){
    if(a<b){
        return a;
    }
    else{
        return b;
    }
}

---

문제 풀이

  코딩을 시작하기 전, 어떤 식으로 문제를 풀어나갈 것인가 계획을 세운 후 코딩에 임하는 습관이 좋습니다. Line 6 ~ 9의 주석이 코딩을 시작하기 전 간략하게 세운 계획입니다.

 

    // color[n][i]: n+1번째 집을 i 색깔로 칠하는 비용 (i=0: 빨강, i=1: 초록, i=2: 파랑)
    // price[n][i]: n+1번째 집을 i 색깔로 칠할 때, 1~n까지 모든 집들을 칠하는 최소 비용
    // price[n+1][0] = min(price[n][1], price[n][2]) + color[n+1][0]
    // 최종 답: price[N-1][0], price[N-1][1], price[N-1][2]의 최솟값

 

  color[N][3]은 각 집을 각 색깔로 칠하는 비용으로, 처음에 입력으로 주어집니다. 구체적으로 color[n][i]는 n+1 번째 집을 i 색깔로 칠하는 비용이며, i=0은 빨강, i=1은 초록, i=2는 파랑을 의미합니다. Line 15 ~ 19에서 color 배열을 모두 채웁니다.

  price[N][3]은 각 집을 특정 색깔로 칠할 때, 그 전까지의 집들까지 모두 칠하는 비용의 최솟값입니다. 예를 들어 price[n][i]는 n+1 번째 집을 i 색깔로 칠할 때, 1 ~ n까지 모든 집들을 칠하는 최소 비용까지 더한 값입니다. 마찬가지로 i=0은 빨강, i=1은 초록, i=2는 파랑을 의미하겠죠?

 

  두 배열 color과 price를 위와 같이 정의하면, 두 배열 간의 관계를 점화식으로 표현할 수 있습니다. n+1 번째 집의 색깔은 n번째 집의 색깔과 달라야한다는 조건이 있으므로, 아래와 같이 표현이 가능합니다.

$$ price[n+1][0] = min(price[n][1], price[n][2]) + color[n+1][0] $$

n+1번째 집을 빨간색으로 칠하기 까지의 최소 비용은, n번째 집을 초록색으로 칠하기 까지의 비용과 파란색으로 칠하기 까지의 비용 중 작은 값과 n+1번째 집을 빨간색으로 칠하는 비용의 합입니다. n+1번째 집을 초록색으로 칠하는 비용 price[n+1][1]과 파란색으로 칠하는 비용 price[n+1][2] 역시 비슷합니다. 이러한 점화식을 토대로 Line 25 ~ 30과 같이 동적 계획법을 사용하면, price 배열을 모두 채울 수 있습니다.

 

for(int i=1; i<N; i++){
    price[i][0] = min(price[i-1][1], price[i-1][2]) + color[i][0];
    price[i][1] = min(price[i-1][2], price[i-1][0]) + color[i][1];
    price[i][2] = min(price[i-1][0], price[i-1][1]) + color[i][2];
    //printf("price[%d][0]: %d, price[%d][1]: %d, price[%d][2]: %d\n", i, price[i][0], i, price[i][1], i, price[i][2]);
}

 

  최종적으로 구해야하는 것은 N번째 집까지 칠하는 비용의 최솟값입니다. N번째 집을 빨간색으로 칠하는 최소 비용은 price[N][0], 초록색으로 칠하는 최소 비용은 price[N][1], 파란색으로 칠하는 최소 비용은 price[N][2]입니다. 세 가지 경우 중 최솟값을 구하면, 최종 답변을 얻게 됩니다.