백준 2293번 - 동전1

백준 2293 - 동전1

문제

• n가지 종류의 동전이 있다.

• 각각의 동전이 나타내는 가치는 다르다.

• 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.

• 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)

입력

• 첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)

• 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.

출력

• 첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

예제 입력

3 10
1
2
5

예제 출력

10

접근

• Dynamic Programming으로 접근한다.

• 첫 번째 동전만 사용하여 각 k값 마다 가능한 경우의 수를 찾는다.

• 첫 번째~두 번째 동전만 사용하였을 때, 각k 값 마다 가능한 경우의 수를 찾는다.이 때, 첫 번째 동전만 사용해서 구했던 경우의 수를 활용한다.

• 첫 번째~n 번째 동전을 사용하였을 때까지 반복한다.

점화식

• ​ : i번째 코인의 가치

• ​ : i번째 코인까지 사용하여 k를 만들 수 있는 경우의 수

풀이

1) 첫 번째 동전만 사용한 경우@

C(i) = [1, 2, 5]
D(i, k) =
        k   0   1   2   3   4   5   6   7   8   9   10
c(0)    [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)    [1] 1   1   1   1   1   1   1   1   1   1   1

2) 두 번째 동전까지 사용한 경우

D(i, k) =
        k   0   1   2   3   4   5   6   7   8   9   10
c(0)    [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)    [1] 1   1   1   1   1   1   1   1   1   1   1
c(2)    [2] 1   1   2   2   3   3   4   4   5   5   6

3) 세 번째 동전까지 사용한 경우

D(i, k) =
        k   0   1   2   3   4   5   6   7   8   9   10
c(0)    [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)    [1] 1   1   1   1   1   1   1   1   1   1   1
c(2)    [2] 1   1   2   2   3   3   4   4   5   5   6
c(3)    [5] 1   1   2   2   3   4   5   6   7   8   10

C++ Code - 1

#include <cstdio>
​
int main() {
    int n, k;
    int c[101];
    int d[101][10001] = {0, };
​
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    
    for (int i = 1; i <= n; i++) {
        d[i][0] = 1;
    }
​
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (j >= c[i]) {
                d[i][j] = d[i - 1][j] + d[i][j - c[i]];
            }
            else {
                d[i][j] = d[i - 1][j];
            }
        }
    }
​
    printf("%d\n", d[n][k]);
​
    return 0;
}

• 위의 점화식을 그대로 구현한 코드

• 메모리를 많이 잡아 먹는다.4 x (101 + 101 x 10001) = 4,080,408 Bytes = 약 3.9 MB + @

• 현재 이 코드를 BOJ에 제출하면 메모리 초과가 난다.

C++ Code 2

#include <cstdio>
​
int main() {
    int n, k;
    int coins[101];
    int d[10001] = {0};
​
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &coins[i]);
    }
    
    d[0] = 1;
​
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (j >= coins[i]) {
                d[j] += d[j-coins[i]];
            }
        }
    }
​
    printf("%d\n", d[k]);
​
    return 0;
}

• i-1번째 경우의 수 배열에 i 번째 경우의 수 배열을 덮어 씌운다.

• 메모리 절약형