백준 11047 - 동전0 - 그리디 알고리즘

문제

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

풀이전략

1. 가치 K를 만드는데 필요한 동전 개수의 최솟값을 찾는다.
2. 따라서 금액이 큰 동전부터 순차적으로 사용 가능 개수를 센다
3. 동전 사용 개수는 K/동전크기, 사용하고 남은 금액은 k%동전크기 를 사용하면 된다.

코드

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int N, K;
vector<int> coin;

int main(){

    // freopen("../input.txt","rt",stdin);
    scanf("%d %d",&N, &K);
    int tmp;
    for(int i=0; i<N; i++){
        scanf("%d",&tmp);
        coin.push_back(tmp);
    }
    int res = 0;
    for(int i=N-1; i>=0; i--){
        res  += K/coin[i];
        K = K% coin[i];

        if(K == 0) break;
    }
    printf("%d\n",res);

    return 0;
}

소감

K와 /, %를 사용한 아이디어가 좋았다.