[2293] 동전 1

문제 링크 : https://www.acmicpc.net/problem/2293

2293 - 동전 1

본문

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
0.5sec	4MB

---

풀이

동전을 여러개 합쳐서 그 가치를 원하는 만큼 만드는 경우의 수를 세는 문제이다.

동전을 이용해 만들 수 있는 가치와 동전의 가치를 합치면, 새로운 가치를 만들어낼 수 있다. 점화식으로도 풀이가 가능하다. 그리고, 점화식으로 풀이가 가능하다는 것은 대부분 dp문제로 해석될 수 있다는 뜻이다. 점화식은 아래와 같이 세울 수 있을 것이다.

\[dp[i] = \sum dp[i-j]\]

이 때 $j$는 문제에서 주어질 수 있는 동전의 가치들이다. 현재 가치가 $7$인데 사용하는 동전의 가치가 $4$라면 우리는 더하여 가치가 $11$인 경우를 만들어낼 수 있다. 이 논리대로 점화식을 코드로 풀어내면 답을 얻을 수 있다.

• 참고 알고리즘 : 다이나믹 프로그래밍

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 30

#include <stdio.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

#define MAX_IDX 10001
    int dp[MAX_IDX] = {0};
    dp[0] = 1;

    for (int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        for (int j = a; j <= k; ++j) {
            dp[j] += dp[j - a];
        }
    }

    printf("%d", dp[k]);
    return 0;
}