[C++] 11047번 동전 0

11047번 문제보기

 

제출코드

#include <iostream>
#include <cassert>

#include <vector>
#include <algorithm>

int main(){
    int answer = 0, n, k;
    std::cin >> n >> k;
    std::vector<int> money;

    // 동전의 종류
    for (int i = 0; i < n; i++) {
        int kind;
        std::cin >> kind;
        money.push_back(kind);
    }

    for(int i=money.size()-1; i >= 0; i--){
        if(k<0) break;
        if(money[i]<=k){
            answer++;
            k -= money[i];
        if(money[i]<=k) i++;
        }
    }
  
    std::cout<<answer;
}

 

풀이

동전을 최소한으로 사용해야 하므로 가장 큰 금액부터 k에서 차감시킨다.

 

후기

쉬운 문제지만 한 번에 맞추지 못했다...

반례를 생각하지 못했다.

마지막 for문에서 범위 지정을 제대로 해주지 않아, 다음 반례에서 막힌 것이었다. 

 

1 500

1

이 결과는 500이 나와야한다.