[백준] 2293 동전1 c++

 

 

그리디알고리즘을 사용한 동전0문제와는 달리

동전1문제는 다이나믹 알고리즘을 사용한다.

 

점화식 생각이 도저히 안나서 풀이를 참고했는데, 봐도 봐도 헷갈리는 개념이었다.

 

핵심은 이거다.

n번째 동전을 한번 쓴 경우 + n번째 동전을 사용하지 않은 경우

예를 들어서 1, 2, 5원짜리 동전으로 10원을 만들려고 할 때, 

5원짜리를 1번 써서 10원을 만든 경우와 5원짜리를 쓰지 않고 10원을 만든 경우로 나눌 수 있다.

이런식으로 계속 내부적으로 나누게 되면 결국 모든 가짓수를 구할 수 있다. 

 

 

 

 

아래 표는 동전단위에 대한 경우의 수를 나타낸 것이다.

                                                                                                   그림출처 https://wtg-study.tistory.com/67

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>
 
using namespace std;
 
int dp[100001];
int arr[101];
int n,k;
 
int main(void)
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
 
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = arr[i]; j <= k; j++)
        {
            dp[j] += dp[j - arr[i]];
        }
    }
    cout << dp[k];
 
    return 0;
}