[그리디]백준 11047번 동전 0 (C++)

 

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

흠..

 

너무쉽다

 

이거 딱봐도 그리디

 

문제 조건에 Ai 가 Ai-1의 배수라 했으니까

 

그냥 간단하게 가장 큰 수부터 작은 수 까지 반복적으로 더해주고, 커지면 다음으로 넘어가면 된다

#include <iostream>

using namespace std;

int main()

{

    int n, k;

    cin >> n >> k;

    int arr[n];

    for (int i = 0; i < n; i++)

    {

        cin >> arr[i];

    }

    int money = 0, count = 0;

    int temp = n - 1;

    while (money != k)

    {

        if (money + arr[temp] > k)

        {

            temp--;

            continue;

        }

        money += arr[temp];

        count++;

    }

    cout << count << "\n";

}

 

Ai 가 Ai-1의 배수라는 것은

 

Ai의 갯수가 적어지면 그만큼 Ai-1의 갯수들이 늘어나니

총 갯수가 무조건 늘어나는 형태인 것이다