[c++] 백준 2293 - 동전 1(점화식)

 

0. 주어진 문제

동전 1 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	4 MB	20194	8189	6034	41.360%

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

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

예제 입력 1 

3 10
1
2
5

예제 출력 1 

10

1. 풀이

처음에는 동전의 가격을 sort()함수를 활용해 정렬한 후, 낮은 가치부터 더해가는 형식으로 구현을 해야겠다고 생각하였지만, 그렇게 구현을 하기란 쉽지 않았다.

따라서, 다른 형태의 구현을 생각하였는데, sum_of_cost[0](0원을 만드는 방법) = 1로 두고, 동전의 가격을 주기로 이전의 방법을 더해주는 형태의 구현이였다.

1) sum_of_cost[j] += sum_of_cost[j - coin_cost[i]]의 형태의 구현인데, 위의 예제를 생각해보자.

우선 1의 가치를 가진 동전이 있으므로, sum_of_cost[0] ~ sum_of_cost[10]은 모두 1이 되게 된다.

2) 2의 가치를 가진 동전이 있으므로,

sum_of_cost[2] = 2,

sum_of_cost[3] = 2,

sum_of_cost[4] = 3,

sum_of_cost[5] = 3,(원래 1에 sum_of_cost[3]의 값인 2가 더해짐)

...

sum_of_cost[10] = 6 이 된다.

3) 5의 가치를 가진 동전이 있으므로,

sum_of_cost[5] = 4 (1 + 3)

sum_of_cost[10] = 10 (4 + 6) 이 된다.

즉, 이러한 형태의 구현을 통해 문제를 해결할 수 있었다.

2. 소스코드

#include<iostream>
 
int coin_cost[101];
int sum_of_cost[10001];
 
int main() {
    int N, K, count(0);
    std::cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        std::cin >> coin_cost[i];
    }
 
    sum_of_cost[0] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            if (j >= coin_cost[i]) {
                sum_of_cost[j] += sum_of_cost[j - coin_cost[i]];
            }
        }
    }
 
    std::cout << sum_of_cost[K];
}

3. 문제 출처

https://www.acmicpc.net/problem/2293

4. 참고