출처: https://cses.fi/problemset/task/1635
문제 설명
Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum x using the available coins.
For example, if the coins are {2,3,5} and the desired sum is 9, there are 8 ways:
- 2+2+5
- 2+5+2
- 5+2+2
- 3+3+3
- 2+2+2+3
- 2+2+3+2
- 2+3+2+2
- 3+2+2+2
입력
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
출력 예
8
제약조건
- 1 <= n <= 100
- 1 <= x <= 10^6
- 1 <= c_i <= 10^6
문제 풀이
특정한 값을 만드는 경우의 수는 코인의 값을 포함하는 경우와 포함하지 않는 경우를 더하면 된다.
먼저, 초기 값으로 목표값이 0인 경우는 아무런 코인도 고르지 않는 empty set 한가지가 된다. (dp[0] = 1) 새로운 코인 값과 기존의 값이 목표값 보다 작은 모든 경우들을 합하면 목표값을 만드는 경우의 수가 된다.
목표값이 xValue가 될때까지 dp[]를 완성하면, dp[xValue] 이 원하는 경우의 수가 된다.
프로그램 내용
...
vector<int> coins(nCoin);
vector<long long> dp(xValue + 1, 0);
for (int idx = 0; idx < nCoin; ++idx)
cin >> coins[idx];
sort(coins.begin(), coins.end());
dp[0] = 1; /// target value == 0, empty set , 1 way
for (int idx = 0; idx <= xValue; ++idx)
for (int id =0; id < nCoin; ++id)
if (idx + coins[id] <= xValue)
dp[idx + coins[id]] += dp[idx];
dp[idx + coins[id]] %= 1000000007;
...
Dynamic Programming ( link )
'CSES' 카테고리의 다른 글
CSES 3. Removing Digits (1637) (0) | 2019.10.14 |
---|---|
CSES 3. Coin Combinations II (1636) (0) | 2019.10.10 |
CSES 3. Minimizing Coins (1634) (0) | 2019.10.09 |
CSES 3. Dynamic Programming (0) | 2019.10.09 |
CSES 2. Array Division (1085) (0) | 2019.10.09 |