BOJ 11047 c++

알고리즘

BOJ 11047 동전 0 c++

백준 11047

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

int n;
int arr[12];
int k;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    int count = 0;
    while (k > 0) {
        if (arr[n] > k) {
            n--;
            continue;
        }
        k -= arr[n];
        count++;
    }
    cout << count;
}

그리디 알고리즘을 이용.

DP를 쓸 수도 있지만 그러면 시간초과가 남.

동전은 배수관계를 갖기 때문에 가장 큰 녀석을 최대한 많이 쓰면 됨.


max_element는 시작주소와 마지막주소 + 1을 넣으면 최대값이 담긴 곳의 주소를 리턴하는 함수.