[C++] 백준 2293 : 동전 1

백준 2293 : 동전 1

 

문제 링크

www.acmicpc.net/problem/2293

2293번: 동전 1

 

 

문제 내용

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

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

 

 

Idea

다이나믹 프로그래밍을 하여 코드를 구현한다.

 

f(n) += f(n-coin) 임을 이용한다.

이때, f(n-coin)을 더해주는 이유는 현재의 가치에서 해당 동전을 사용한다 했을 때 남은 가치의 경우의 수를 더해주기 위함이다.

 

아래 표는 각 가치에 대한 경우의 수를 나타낸 것이다.

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	3	3	4	4	5	5	6
5	1	2	2	3	4	5	6	7	8	10

 

 

Code

#include <stdio.h>
int dp[100001];
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
 
    //동전 배열 크기 동적 할당
    int* coin = new int[n];
 
    //동전의 가치 입력
    for (int i = 0; i < n; i++)
        scanf("%d", &coin[i]);
 
    //경우의 수 구하기
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = coin[i]; j <= k; j++) {
            dp[j] += dp[j - coin[i]];
        }
    }
 
    printf("%d\n", dp[k]);
    return 0;
}