출처: https://cses.fi/problemset/task/1636
문제 설명
Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum xx using the available coins.
For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:
- 2+2+5
- 3+3+3
- 2+2+2+3
입력
The first input line has two integers n and x: the number of coins and the desired sum of money.
The second line has n distinct integers c_1,c_2,…,c_n: the value of each coin.
출력
Print one integer: the number of ways modulo 10^9+7
입력 예
3 9
2 3 5
출력 예
3
제약조건
- 1 <= n <= 100
- 1 <= x <= 10^6
- 1 <= c_i <= 10^6
문제 풀이
특정한 값(a)을 만드는 경우의 수를 dp(a) 라고 하고, 특정한 코인의 값을 coin(b)라고 하면, 코인 coin(b)를 추가해서 a값을 완성하는 경우와 사용하지 않고 완성하는 경우의 합으로 계산할 수 있다.
dp(a, b) = dp(a, 0) + dp(a - coin(b))
0 값을 만드는 방법은 아무것도 고르지 않는 empty set의 한가지 경우 밖에 없으므로, dp(0) = 1이 된다.
또, dp(coin(a)) = 1, 특정 코인 1개로 표현할 수 있는 방법 1에서 다른 경우들을 완성해서 목표로 하는 값을 찾는 문제이다.
프로그램 내용
...
vector<int> coins(nCoin,0);
vector<long> dp(tValue+1, 0);
for (int idx=0; idx < nCoin; ++idx)
cin >> coins[idx];
sort(coins.begin(), coins.end());
dp[0] = 1;
for (int idx = 0; idx < nCoin; ++idx)
for (int id = coins[idx]; id <= tValue; ++id)
dp[id] = (dp[id] + dp[id - coins[idx]]) % 1000000007;
...
Dynamic Programming ( link )
'CSES' 카테고리의 다른 글
CSES 2. Sliding Median (1076) (0) | 2019.12.25 |
---|---|
CSES 3. Removing Digits (1637) (0) | 2019.10.14 |
CSES 3. Coin Combinations I (1635) (0) | 2019.10.09 |
CSES 3. Minimizing Coins (1634) (0) | 2019.10.09 |
CSES 3. Dynamic Programming (0) | 2019.10.09 |