[CodeUp] #2634-거스름돈 II(관계기반 설계)

#include <iostream>
#include <vector>
using namespace std;

vector<int> coin;

int ans = 0;
void func(int m,int cnt,int index){

    if(m==0 && index < 0){
        if(ans!=0){
            if(ans > cnt){
                ans = cnt;
                return;
            }
        }
        else{
            ans = cnt;
            return;
        }
    }

    if(m<0 || index<0 || (ans!=0 && ans < cnt)){
        return;
    }

    for(int i=int(m/coin[index]);i>=0;i--){
        func(m-coin[index]*i,cnt+i,index-1);
    }
    return;
    
}


int main(){
    int money, type;
    cin >> money >> type;
    coin.resize(type,0);

    for(int i=0;i<type;i++){
        cin >> coin[i];
    }

    func(money,0,coin.size()-1);

    cout << ans;

}