백준 11047 (동전 0) / C++

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

11047번: 동전 0

> 풀이

 

최솟값을 구한다에서 dp를 떠올릴 수도 있겠지만, 데이터 범위가 1억까지이기 때문에 힘듭니다.

 

조건을 보시면 가장 작은 동전의 단위는 1원이고, 모든 동전은 이전 동전의 배수이기 때문에 가장 큰 동전부터 빼나가시면 됩니다.

#include <bits/stdc++.h>
using namespace std;

int N, K, cnt, coin[10];

int main(void) {
        scanf("%d %d", &N, &K);
        for (int i = 0; i < N; i++) scanf("%d", &coin[i]);

        for (int i = N - 1; i >= 0;) {
                if (coin[i] > K) {
                        i--;
                        continue;
                }

                K -= coin[i];
                cnt++;
        }

        printf("%d", cnt);
        return 0;
}