[백준/C++] 11047번 동전 0

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

문제

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

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

그리디 알고리즘 중에서도 쉬운편에 속하는 문제입니다. 최솟값을 k를 만들기 위해 n개의 종류의 동전을 이용해 만들때 필요한 최소 동전 갯수를 구하는 문제입니다. 여기서 종류별로 동전은 무제한이니 한 종류의 동전을 여러번 사용해도 문제가 없다는 것이 이번 문제의 핵심입니다.

사용한 동전 개수의 최솟값을 구하기 위해선 k보단 작지만 가치가 가장 큰 동전을 최대한 많이 사용하여야 합니다.

 

answer+=k/coins[i];
k = k%coins[i];

저는 k보다 숫자가 큰 동전의 종류는 입력을 받지 않았고 k보다 크기가 작은 동전들만 vector<int>coins 벡터에 담아 주었습니다. 그리고 벡터의 뒤부터 (문제에서 오름차순으로 입력을 주어 맨 뒤부터 검사하면 제일 큰 크기의 동전부터 탐색하기 시작)시작하여  '/','%' 연산으로 동전의 개수를 구해주었습니다.

 

전체 소스코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    long long k;
    int num;
    vector<long long>coins;
    int answer = 0;
    cin>>n>>k; // n : 동전의 갯수 , k : k 원
    
    for(int i=0;i<n;i++)
    {
        cin>>num;
        if(num>k)
            continue; //k보다 큰 동전은 필요없다.
        coins.push_back(num);
    }
    
    for(int i=coins.size()-1;i>=0;i--)
    {
        answer+=k/coins[i];
        k = k%coins[i];
        
        if(k==0)
            break;
    }
    
    cout<<answer<<endl;
    
    return 0;
}