예산 - 1단계 (C++)

이 문제에를 풀 때 조합으로 문제를 풀려했었는데, 그게 아니었습니다. 문제에서 원하는 답은 얼마나 많은 부서에 금액을 지원해 줄 수 있는지 즉, 부서의 최대 부서 수를 물어보는 거였지, 그 예산에 딱 맞춰서 예산을 줄 수 있는 부서를 물어보는 것이 아니었습니다.

 

물론, 문제에서 예산이 남으면 안될 것 같지만, 다시 한 번 말씀 드리자면 원하는 건 부서의 수지 예산이 아닙니다. 그러니 우리는 부서를 중심으로 생각할 필요가 있고 이를 코드로 나타냈습니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm> // sort를 쓰기 위함

using namespace std;

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