C 언어로 풀는 동전 교환(Coin Change) 문제 – 동적 계획법으로 조합의 수 구하기

이 글에서는 동전 교환(Coin Change) 문제를 C 언어와 동적 계획법(Dynamic Programming)으로 해결하는 방법을 알아봅니다.

문제 정의

금액 n이 주어졌을 때, 가치가 서로 다른 m개의 동전을 사용하여 정확히 n원을 만드는 모든 조합의 개수를 구하는 것이 목표입니다. 단, 동전의 순서만 다른 경우는 같은 조합으로 간주합니다.

예시

입력 : N = 6 ; coins = {1, 2, 4}
출력 : 6
설명 : 합이 6이 되는 전체 조합은 다음과 같습니다.
{1,1,1,1,1,1} ; {1,1,1,1,2} ; {1,1,2,2} ; {1,1,4} ; {2,2,2} ; {2,4}

해결 아이디어

이 문제는 2차원 DP 테이블을 활용하면 효율적으로 풀 수 있습니다.

• table[i][j] = j번째 동전까지 사용했을 때 금액 i를 만드는 조합의 수
• x : 현재 동전 S[j]를 한 번 더 사용하는 경우 → table[i - S[j]][j]
• y : 현재 동전을 사용하지 않고 이전 동전들로만 만드는 경우 → table[i][j-1]
• 두 경우를 더한 값이 곧 table[i][j]가 됩니다.

기저 조건으로 금액이 0일 때는 어떤 동전이든 사용하지 않는 한 가지 방법이 존재하므로, 테이블의 첫 행을 모두 1로 초기화합니다.

C 언어 구현 코드

#include <stdio.h>
int coins(int S[], int m, int n) {
    int i, j, x, y;
    int table[n+1][m];
    for (i = 0; i < m; i++)
        table[0][i] = 1;
    for (i = 1; i < n+1; i++) {
        for (j = 0; j < m; j++) {
            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
            y = (j >= 1)? table[i][j-1]: 0;
            table[i][j] = x + y;
        }
    }
    return table[n][m-1];
}
int main() {
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = 4;
    printf("%d을(를) 만드는 동전 조합의 총 개수", n);
    printf("는 %d개 입니다.", coins(arr, m, n));
    return 0;
}

실행 결과

4을(를) 만드는 동전 조합의 총 개수는 4개 입니다.

코드 설명

동전 {1, 2, 3}으로 금액 4를 만드는 조합은 {1,1,1,1}, {1,1,2}, {2,2}, {1,3}의 네 가지입니다. 이 알고리즘의 시간 복잡도는 O(n × m), 공간 복잡도 역시 O(n × m)으로, 완전 탐색에 비해 훨씬 효율적으로 모든 조합의 수를 계산할 수 있습니다.