백준 11047 동전 0 / C++

문제 : 11047

풀이 point

그리디 활용 문제

동전의 가치는 각각 배수관계(이 말이 없으면 풀이가 달라질 수 있음)
동전 가치의 합을 K로 만들기 위해 필요한 최소 동전 개수를 구하기
가장 큰 동전부터 처리해나가면 가장 최소 갯수로 처리할 수 있겠다는 생각이 든다.

풀이 방법

생각한 것을 구현한다.
동전은 오르차순으로 주어지므로 동전 가치를 입력받은 후
for문을 뒤에서 부터 진행하여 4200원으 0으로 만들면 된다.

코드

//백준 11047, 동전 0

#include <iostream>
#include <vector>
#include <queue>

int main(){
    
    int N, K;
    std::cin >> N >> K;
    int v[N];

    for(int i{0}; i<N; ++i) std::cin >> v[i];

    int k = K;
    int cnt{0};
    
    for(int i{N-1}; i>=0; --i){
        if(k == 0) break;
        if(k / v[i] == 0) continue;
        cnt += k/v[i];
        k = k - v[i] * (k/v[i]);
    }

    std::cout << cnt;
    return 0;
}