문제

링크

풀이

문제 조건에서 "Ai는 Ai-1의 배수"라는 조건이 있어 그리디로 풀 수 있었다.

조건이 없으면 그리디로 풀 수 없다.
그 이유는 탐욕법(그리디) 에 반례를 들어 설명해두었다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

bool cmp(int a, int b){
    return a > b;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K, cnt=0;
    cin >> N >> K;
    vector<int> coin;

    for(int i=0;i<N;i++){
        int tmp;
        cin >> tmp;
        coin.push_back(tmp);
    }

    sort(coin.begin(), coin.end(), cmp);

    for (int i = 0; i < N; i++)
    {
        if(K/coin[i] == 0)continue;
        cnt += K/coin[i];
        K = K%coin[i];
    }

    cout << cnt;

    return 0;
}