백준 2294번 - 동전 2

https://www.acmicpc.net/problem/2294

지난번에 풀었던 동전 1 과 유사한 문제다.
차이점은 동전 1의 경우 가능한 모든 경우의 수를 구하는 문제였다면
동전 2는 최소의 동전을 사용해서 k의 가치를 만들면 되는 문제이다.



dp[n]을 n이라는 값을 구하기 위해 필요한 최소 동전의 개수라고 가정할 때,
먼저 dp[0]에 1이라는 값을 설정하자.
그리고 순서대로 동전의 가치만큼 값을 구해 나가면 된다.




조건문을 실행할 때 주의를 해야 하는데 처음부터 살펴보면 dp[0]에 값이 1이 있다.




그리고 처음 동전의 가치가 1이라고 한다면
dp[0+1]을 구할 때 dp[0]의 값에 1을 설정했기 때문에 dp[0+1]의 가치를 구하면 된다.


만약에 dp[1]을 구하는 경우가 없었다면 dp[0]의 값에 1을 더해주면 된다.
만약에 dp[1]의 값이 존재한다면 dp[0]에 1을 더한 값과 기존의 dp[1]의 값을 비교해서
최소로 필요한 동전의 개수를 구하면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    
    int n,k;
    cin>>n>>k;
    
    int arr[101];
    int dp[10001]={0};
    
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
    }
    
    //0+arr[1],1+arr[1]
    //0+arr[2],1+arr[2]
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j+arr[i]<=k;j++){
            if(dp[j]){
                if(dp[j+arr[i]]==0)
                    dp[j+arr[i]]=dp[j]+1;
                else
                    dp[j+arr[i]]=min(dp[j+arr[i]],dp[j]+1);
            }
        }
    }
    
    cout<<dp[k]-1<<endl;
    
    return 0;
}