[Greedy] 백준 11047번 - 동전 0

 

 

동전을 최대한 적게 이용하려면 큰 값의 동전부터 넣어보아야 한다.

 

예를 들어 6500원을 만들어야 하고 1000원이 가장 큰 돈 단위라면

 

1000원부터 6장 넣고 그다음에 남은 500원을 처리하는 것이 더 효율적이다

 

하지만!

 

큰 단위의 동전을 넣을 수 있는 만큼 넣었는데 나머지 돈 단위로 해결할 수 없는 애매한 잔액이 남았다면?

 

그렇다면 한단계 전으로 돌아가서 뺀 다음에 다시 진행

 

Case 1) 선택한 동전으로 차감할 수 있는 경우

 

선택한 동전이 K보다 작아야 한다

 

Case 2) 선택한 동전으로 차감 불가한 경우

 

다음 작은 동전으로 넘어간다

 

애초에!!!!

Case 1만 남기기 위해 사전에 값을 넣을 때 K보다 큰 수는 vector에 넣지 않는다

 

 

최대로 차감할수 있는 동전의 개수를 아는 법 : 남은 돈 / 동전의 단위

K에서 동전의 개수 x 금액의 수를 빼주면서 

0이 될 때까지 while 문을 돌아주자!

 

vector에서 pop_back()은 가장 마지막에 있는 원소를 erase해주는 것!

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;

int N, K, total;
int input;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin>>N>>K;

    vector<int> v;

    for(int i=0; i<N; i++){
        cin>>input;
        if(input <= K)
            v.push_back(input); // 애초에 K보다 큰 원소는 넣어주지도 않을거야
    }
    int tmp=0;
    int mul=0;
    while(K!=0){
        tmp = v[v.size()-1];
        mul = (int)(K/tmp);	//예를 들어 4500원을 1000원짜리 몇장까지 커버 가능? 에서 몇장을 구하는것
        K -= mul * tmp; //몇장까지 커버 가능한지 알았으면 원래 가격에서 빼준다
        total += mul;
        v.pop_back(); //벡터 리스트에서 지워주고! 그래야 저 위에 size()-1했을 때 그 다음 작은 지폐가 나오지
    }
    cout << total;

}