2293: 동전 1

• toc {:toc}

문제 확인하기

풀이

규칙 찾는 것이 힘들다. dp문제를 많이 풀어봐야 할 것 같다.
1, 2, 3을 사용하고 k=3인 경우를 생각해보자.

사용 동전	1	2	3
1원	1	1	1
2원	0	1	0
3원	0	0	1
1, 2원	1	2	2
1, 2, 3원	1	2	3

• 1원만 사용해 만들 수 있는 경우 1원 1개를 사용해 1원 만들기
  1원 2개를 사용해 2원 만들기
  1원 3개를 사용해 3원 만들기

• 2원을 사용해 만들 수 있는 경우 2원 1개를 사용해 2원 만들기
  2원 1개, 1원 1개를 사용해 3원 만들기

• 3원을 사용해 만들 수 있는 경우 3원 1개를 사용해 3원 만들기

2원, 3원의 경우 사용 동전보다 작은 경우는 만들 수 없다.

3원을 만들려는 경우는 3원 1개를 사용하는 경우, 2원 1개와 1원 1개를 사용하는 경우, 1원 3개를 사용하는 경우로 확인할 수 있다. 이를 dp로 생각해보면 dp[3] = 1 의 경우 “3원을 만들려는 경우의 수는 1개”로 생각할 수 있다.

1. 3원 1개를 사용하는 경우 dp[3] += dp[0] 으로 표현할 수 있다. 3원을 사용하는 경우 기존에 있어야 할 동전이 없기 때문에 0을 없는 경우로 구현한다.
2. 2원 1개를 사용하는 경우 dp[3] += dp[1] 로 표현한다. 2원 1개를 사용하는 경우 기존에 1원 1개가 있어야 하기 때문에 1원을 만드는 경우를 더해준다.
3. 1원 1개를 사용하는 경우 dp[3] += dp[2] 로 표현한다. 1원 1개를 사용하는 경우 기존에 2원 1개가 있어야 하기 때문에 2원을 만드는 경우를 더해준다.

때문에 해당 동전을 사용해 만들려면 만들려는 동전의 수에서 해당 동전을 빼주는 방식으로 구현한다.
ex) 2원을 이용해 3원을 만들려는 경우 : dp[3 - 2]

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
 
int coin[105];
int dp[10005];
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n, k;
 
    cin >> n >> k;
 
    for(int i = 1; i <= n; i++){
        cin >> coin[i];
    }
 
    dp[0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = coin[i]; j <= k; j++){
            dp[j] = dp[j] + dp[j - coin[i]];
        }
    }
 
    cout << dp[k] << endl;
 
    return 0;
}