백준 11047번 동전 0

문제 링크입니다: https://www.acmicpc.net/problem/11047

가치가 큰 동전부터 더해나가는 것이 핵심이였습니다.

/*

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만드려고 한다.

이 때 필요한 동전 개수의 최소값을 구하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <vector>

using namespace std;

 

int N; //동전 수

int total; //총합

vector<int> v;

 

int minCoin(void)

{

        int cnt = 0;

        for(int i=v.size()-1; i>=0; i--) //가치가 큰 동전부터 빼야 최소 반환

               while (total - v[i] >= 0)

               {

                       total -= v[i];

                       cnt++;

                       if (!total) //합을 만들어냈다면

                              break;

               }

        if (total)

               return 0; //가진 동전으로 합을 만들 수 없다면

        return cnt;

}

 

int main(void)

{

        cin >> N >> total;

        if (N < 1 || N>10 || total < 1 || total>100000000)

               exit(-1);

        for (int i = 0; i < N; i++) //이미 오름차순으로 입력

        {

               int value;

               cin >> value;

               v.push_back(value);

        }

        cout << minCoin() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략