coin1-2293

• 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;
}