[c++] 백준 2294 동전 2

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

2294번: 동전 2

#include<bits/stdc++.h>
using namespace std;
#define INF 987654321
vector<int> coin;
int dp[111111];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k; cin>>n>>k;
    //최소를 구해야하기 때문에 큰 값으로 초기화 해준다.
    for(int i=0; i<10010; i++) dp[i] = INF;
    //입력 받기
    for(int i=0; i<n; i++){
        int k; cin>>k;
        dp[k]=1;
        coin.push_back(k);
    }
    //인덱스 생각하기 귀찮아서 그냥 최대치(10000)까지 반복돌림
    for(int i=0; i<=10000; i++){
        // i원을 지불할 수 있는 경우가 있으면
        if(dp[i] != INF){ 
            for(auto j : coin){ // 동전 가치 불러오기
                if(i+j > 10000) continue; // 배열 범위 초과 예방
                // 업데이트 할 곳에 이미 최소일수 있음
                dp[i+j] = min(dp[i+j], dp[i]+1);
            }
        }
    }
    // 업데이트가 안되어있다 => 지불 불가한 경우
    if(dp[k] == INF) cout << -1;
    //출력
    else cout << dp[k];
    return 0;
}