[BOJ/C++] 동전 0(11047번)

1. 개요

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

11047번: 동전 0

1-1. 설명

준규가 가지고 있는 동전은 총 N 종류이며, 동전을 매우 많이 가지고 있다. 이 동전을 적절히 사용해 가치의 합 K를 만드려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 N과 K가 주어지며 N은 1 이상 10 이하, K는 1이상 100,000,000 이하

 - 둘째 줄부터 N개의 줄에 동전 가치 A_i가 오름차순으로 주어짐

 - A_i는 1 이상 1,000,000 이하, A_i = 1, i >= 2인 경우 A_i는 A_i-1의 배수

---

2. 구현

2-1. 풀이

반복문을 통해 내림 차순으로 동전을 확인하며 빼주었다. 

2-2. 코드

#include <iostream>
using namespace std;

int moneys[10];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N, K, result = 0, index = 0;
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> moneys[i];
    }

    for (int i = N - 1; i >= 0; i--) {
        if (K >= moneys[i]) {
            while (K >= moneys[i]) {
                K -= moneys[i];
                result += 1;
            }
        }
        if (K == 0) break;
    }

    cout << result << "\n";

    return 0;
}