[C++] 프로그래머스 예산 S사

#include <algorithm>
#include <vector>

using namespace std;

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

dfs 방식으로 풀면 된다고 생각했다. 

d 벡터를 돌면서 해당하는 인덱스의 값을 더할건지 아무런 연산도 안할건지 하면서 두 개의 노드로 뻗어나가면 되는 줄 알았다.

투머치한 풀이였다. 물론 시간초과나서 정답 근처도 못갔다.

이건 그냥 예산에 일치할 때까지 얼마나 많은 개수를 담을 수 있는지의 여부이다. 

그러면 제일 작은 값들을 위주로 담아야 많이 담을 수 있으니 오름차순 정렬 후에 sum <= budget을 만족할 때까지 answer++ 하면 된다.