[백준 1149번/C언어] RGB거리, 동적계획법으로 풀이

백준 1149번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 

백준 1149번: https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

문제 내용은 아래와 같습니다. 예제 입출력이 더 준비되어 있으니, 위 링크를 통해 확인하시기 바랍니다.

 

이 문제 역시 이전에 업로드한 다른 DP를 이용한 문제와 마찬가지로 동적계획법 학습을 위해 푼 문제입니다. 따라서 동적계획법에 익숙하지 않으시다면, 아래 블로그를 참고해 주시기 바랍니다. 저 역시 동적계획법 문제를 처음 접해보기 때문에 다양한 글들을 꼼꼼히 읽어본 후, 가장 기초적인 문제부터 풀고 있습니다. 

https://didu-story.tistory.com/220

[알고리즘] Dynamic Programming (동적 계획법, DP) (feat. Swift 스위프트)

 

동적계획법을 이용하기 위해서는, 동적계획법의 핵심인 점화식을 우선적으로 파악해야 합니다. 이 문제를 풀 때 점화식을 파악하는 데 정말 오랜 시간이 걸렸습니다. 왜냐하면 결괏값이 경우에 따라 너무 크게 달라지기 때문입니다. 결론부터 이야기하자면, 해당 문제는 dp값을 3가지 경우로 나누어 저장해 가며 계산해야 하는 문제입니다. 즉 점화식을 굳이 정리해보자면, 아래와 같습니다. 

C(n번째 red) = C(n-1번째 green과 blue 중 더 작은 값) + n번째 red cost
C(n번째 green) = C(n-1번째 red와 blue 중 더 작은 값) + n번째 green cost
C(n번째 blue) = C(n-1번째 red과 green 중 더 작은 값) + n번째 blue cost

이후 결과값을 n번째 red, green, blue 중 가장 작은 값으로 출력하면 됩니다. 

 

여기까지만 파악하면 코드를 구현하는 것은 그리 어려운 일이 아닙니다. 아래와 같이 이차원 배열을 두 개 만들어서 cost배열은 입력받은 비용을 저장하는 용도로 쓰고, dp배열은 1~n번째까지의 최소 비용들을 저장해 두는 데 사용합니다. 

dp의 0번째 배열에는 cost를 그대로 입력하고, 그 이후부터는 위 점화식에 따라서 현재 cost와 + 이전까지 다른 색들의 cost 중 작은 값을 더해줍니다. 마지막으로 minimum을 찾아서 출력해주면 끝입니다. 

#include <stdio.h>
#include <stdlib.h>

// 2차원 배열에 저장할 위치에 따라 각 숫자를 색깔명으로 define
#define RED 0
#define GREEN 1
#define BLUE 2

// 값 두 개를 argument로 받아 더 작은 값을 return 하는 compare 함수
int compare(int a, int b) {
    if (a > b) return b;
    else return a;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int (*cost)[3] = (int(*)[3])malloc(sizeof(int) * 3 * n);
    for (int i = 0; i < n; i++) scanf("%d %d %d", &cost[i][RED], &cost[i][GREEN], &cost[i][BLUE]);
    
    // dp 배열에 bottom up 방식으로 첫번째 비용부터 차례로 저장해가며 n까지 도달하도록 함
    int (*dp)[3] = (int(*)[3])malloc(sizeof(int) * 3 * n);
    dp[0][RED] = cost[0][RED];
    dp[0][GREEN] = cost[0][GREEN];
    dp[0][BLUE] = cost[0][BLUE];
    
    // 세운 점화식을 기반으로 결괏값을 dp 배열에 저장
    for (int i = 1; i < n; i++) {
        dp[i][RED] = cost[i][RED] + compare(dp[i-1][BLUE], dp[i-1][GREEN]);
        dp[i][GREEN] = cost[i][GREEN] + compare(dp[i-1][BLUE], dp[i-1][RED]);
        dp[i][BLUE] = cost[i][BLUE] + compare(dp[i-1][RED], dp[i-1][GREEN]);
    }
    
    // n번째 (배열 index = n-1) 결괏값 중 최솟값을 출력
    int min = compare(dp[n-1][RED], dp[n-1][GREEN]);
    min = compare(min, dp[n-1][BLUE]);
    printf("%d", min);
    
    free(cost);
    free(dp);
}