[DP/난이도 중하] 동전 2(다시한번 풀어보기)

어떻게 풀어야 될지 감이 잘 안와서 구글링을 해서 풀었다..

1원짜리 5원짜리 12원짜리 동전이 있고 15원을 만드려고 할때 최소의 동전개수로 만드는 문제이다.

이문제는 동전교환 문제라고 알려진 유명한 문제이다

맨 위의 굵은 숫자들은 몇원이냐를 말하는것이다. 1원,2원,3원...을 만들기 위해 필요한 최소의 동전의 개수가 저장된다.

1     2     3    4    5    6    7    8    9    10    11    12    13    14    15

1     2     3    4    5    6    7    8     9     10     11    12    13    14    15  =>동전이 1원짜리만 있다고 가정

                          1    2    3     4     5      2     3     4      5      6     3   => 1원짜리와 5원짜리가 있다고 가정

                                                                         1        2      3     3   => 1원,5원,12원짜리가 있다고 가정했을때 필요한 최소 동전의 개수

해서 답은 총 3개의 동전이 필요하다

위의 숫자들은 dp[1~15]까지 들어가는 숫자들을 나타낸 것이다.

현재 동전이 1원짜리만 있다고 가정

1원을 만들려고 할때 1원짜리 1개

2원->1원2개

...

15원 -> 1원 15개

5원짜리가 있다고 가정했을때 바뀌는 부분은 5~15원 사이다.

또한 12원짜리가 있다고 가정했을때 바뀌는 부분은 12~15원 사이다.

#include<iostream>
#include<algorithm>
 
using namespace std;
int input[10001];
int dp[10001];
int n,k;
 
 
int main()
{
    cin>>n>>k;
    
    for(int i=1; i<=n; i++)
        cin>>input[i];
    
    for(int i=1; i<=k; i++)
        dp[i] = 99999999;       //이래야 min(,)을 했을때 맨 첫줄이 제대로 채워진다.
    dp[0] = 0; 
    
    for(int i=1; i<=n; i++)
    {
        for(int j = input[i]; j<=k; j++)
        {
            dp[j] = min(dp[j],dp[j-input[i]]+1);
        }
    }
    if(dp[k] == 99999999)
        cout<<-1<<endl;
    else
        cout<<dp[k]<<endl;
    
    
    return 0;
}