[Lv 1] 예산

https://school.programmers.co.kr/learn/courses/30/lessons/12982

프로그래머스

 

이 문제는 그리디 알고리즘을 사용해서 해결할 수 있다.

문제를 보면 가능한 많은 사람을 사용해서 budget에 해당하는 금액을 맞춰야한다는 것을 알 수 있다.

따라서 d배열에 있는 값을 정렬한 후 앞에서 부터 budget이 0이 되기 전까지 사람 수를 세면 최대 지원 부서 수를 알 수 있다.

 

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int solution(vector<int> d, int budget) {
    int answer = 0;
    
    sort(d.begin(), d.end());
    
    for(int i = 0;i<d.size();i++){
        int coin = d[i];
        budget -= coin;
        if(budget >= 0)
            answer += 1;
    }
    return answer;
}