출처: https://cses.fi/problemset/task/1634
문제 설명
Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to produce a sum of money x using the available coins in such a way that the number of coins is minimal.
For example, if the coins are {1,5,7} and the desired sum is 11, an optimal solution is 5+5+1 which requires 3 coins.
입력
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 minimum number of coins. If it is not possible to produce the desired sum, print -1.
입력 예
3 11
1 5 7
출력 예
3
제약조건
- 1 <= n <= 100
- 1 <= x <= 10^6
- 1 <= c_i <= 10^6
문제 풀이
코인의 종류와 목표값을 입력 받고, 코인들의 값을 입력 받는다. 목표값이 0인 경우 최소 코인은 0개가 되고, 목표값이 특정한 코인의 값과 같은 경우에 필요한 코인 최소 개수는 1개가 된다. 목표값을 1 부터 x 까지 이동해가면서 코인들을 포함 시키는 경우들에 대해서 검사해서 값을 변경한다. dp[x] 가 원하는 값이 된다.
(dp[target], coin[j]) check dp[target-coin[j]] >0
- dp[target] == initial value(-1) -> dp[target] = dp[target-coin[j]] + 1
- dp[target] != initial value -> compare min(dp[target], dp[target-coin[j]] +1)
프로그램 내용
...
vector <int> coins(N);
vector <long> dp(MAX_T+1, -1);
for(int idx = 0; idx < N ; ++idx)
cin >> coins[idx];
dp[coins[idx]] = 1; // target == coin_value, minimum coin 1
sort(coins.begin(), coins.end()); /// coin value low to high
dp[0] = 0; /// target = 0, no coin
/// Compute minimum coins required for all values from 1 to target
for (int i=1; i<=target; i++)
/// Go through all coins smaller than i
for (int j=0; j < N; j++)
if (i <= coins[j] ) continue; // skip current coin
if ( dp[i - coins[j]] >= 0) // check current coin use or not
if (dp[i] == -1) // not updated target value
dp[i] = 1 + dp[i-coins[j]];
else // add current coin to meet the target value
dp[i] = min(dp[i], 1 + dp[i-coins[j]]);
...
Dynamic Programming ( link )
'CSES' 카테고리의 다른 글
CSES 3. Coin Combinations II (1636) (0) | 2019.10.10 |
---|---|
CSES 3. Coin Combinations I (1635) (0) | 2019.10.09 |
CSES 3. Dynamic Programming (0) | 2019.10.09 |
CSES 2. Array Division (1085) (0) | 2019.10.09 |
CSES 2. Subarray Divisibility (1662) (0) | 2019.10.09 |