백준 11047번 - 동전 0

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

필요한 동전 개수를 구하면서 처음에는 dp로 문제를 접근했다.

dp[i]를 i번째의 동전 가치를 구하는데 필요한 최소 동전의 개수라고 했을 때
dp[0]을 1로 지정한 다음에 순차적으로 K까지 필요한 동전의 최소 개수를 구하도록 했다.
그런데 문제의 조건을 보면 N의 최대 값이 10이고 K가 1억이다.
K만큼 배열 크기를 고정하다보니 메모리 초과가 났다...


결국 그리디로 문제를 해결할 수 있었다.
동전의 가치가 큰 순서대로 K라는 가치의 합을 구할 때 몇개가 필요한지 구했다.
만약에 K보다 해당 동전의 가치가 크다면 이보다 작은 동전의 가치로 나눠주도록 했다.

최소 동전의 개수라는 답을 구하기 위해서는
K라는 동전의 가치를 넘지 않는 조건에서 가장 큰 동전의 가치로 나눠주는 것이 최적의 답인 것이다. 


그리디 방법은 현재의 상황에서 최적의 답을 구하는 것이기 때문에 증명이 필요한 방법인데
그래도 이 문제는 수학적으로 쉽게 생각할 수 있는 문제여서 바로 그리디로 접근할 수 있었다.

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    
    int N,K;
    cin>>N>>K;
    
    vector<int> coin(N,0);
    for(int i=0;i<N;i++)
        scanf("%d",&coin[i]);
    
    int ans=0; //사용되는 동전 개수
    for(int i=N-1;i>=0;i--){
        
        if(K==0)
            break;
        
        if(coin[i]>K)
            continue;
        
        ans+=K/coin[i];
        K%=coin[i];
    }
 
    cout<<ans<<endl;
    
    return 0;
}