예산

들어가는 말

주어진 예산 안에서 제일 많은 부서를 챙겨주는 문제이다. 여기서 부서가 신청한 금약은 줄어들거나 늘어나지 않는다.
이 문제를 보고 제일 먼저 생각한 건 잔돈 거슬러주기 알고리즘이다. 잔돈 거슬러주기는 제일 큰 값부터 골라 예산을 맞췄는데, 최대한 많은 부서가 포함되어야 하니 제일 작은 값부터 포함시켜야 한다.

코드 설명

먼저 sort함수를 써서(이제는 나름 자유자재로 쓴다) 오름차순으로 배열을 정렬해주었다. 그후 예산이 찰 때까지 작은 값부터 더해주는데, 만일 예산이 넘지 않으면 답의 수를 증가시켜준다. 마침내 예산이 넘으면 break로 탈출한다.

코드

#include <vector>
#include <algorithm>

using namespace std;

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