[백준] 11047번: 동전 0(C++) 풀이 및 해설

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

11047번: 동전 0

 

풀이

가장 기초적인 그리디 알고리즘 문제다.

동전을 가장 적게 가져가기 위해서는 , 큰 금액의 동전이 최대면 된다.

즉, 일단 총금액에서 최대의 동전을 가져갈 수 있을 만큼 가져가고,

그다음 크기의 동전을 가져갈 수 있을 만큼 가져가고..

 

이걸 반복하면 된다.

 

예를들어 1260원이 있다 치면

500원으로 최대개수인 2개 가져가고, 260원이 남았으니 

100원으로 최대개수인 2개 가져가고, 60원이 남았으니

50원으로 최대개수인 1개 가져가고, 10원이 남았으니

10원 1개 가져가서

동전은 총 6개 가져가면 된다.

 

해답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main()
{
    fastio;
    int n,k,ans=0;
    cin>>n>>k;
    int arr[n];
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    int j=0;
    while(k>0){
        if(arr[n-j-1]<=k){
            k-=arr[n-j-1];
            ans++;
        }
        else{
            j++;
        }
    }
    cout<<ans;
  

    return 0;
}

 

 

 

코드 설명

우선 n만큼 크기를 가진 금액 개수 리스트 arr을 만들고, for문으로 입력받은 금액리스트를 저장해 준다.

그리고 while문으로 큰 금액을 뺄 수 있다면 주어진 금액에서 빼준다.