[프로그래머스] 예산

풀이 1

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

using namespace std;

int solution(vector<int> d, int budget) {
    int answer = 0;
    vector<int> index = {0};
    sort(d.begin(), d.end());
    answer += d[0];
    int i = 1;
    while (answer != budget){
        if (answer + d[i] < budget){
            answer += d[i];
            index.push_back(i);
            i++;
        } else {
            answer -= d[index[index.size()-1]];
            index.pop_back();
        }
    }
    return answer;
}

signal: aborted (core dumped) 에러 발생으로 불가능

풀이 2

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

using namespace std;

int solution(vector<int> d, int budget) {
    int answer = 0;
    vector<int> side(d.size(), 1);
    int sum = 0;
    for(int i = 0; i < d.size(); i++){
        do {
            sum = 0;
            for (int j = 0; j < d.size(); ++j) {
                if (side[j] != 0) {
                    sum += d[j];
                }
            }
            if (sum == budget){
                return d.size() - i;
            }
        } while (next_permutation(d.begin(), d.end()));
        side[i] = 0;
    }
    return answer;
}

시간 초과 및 2, 6 테스트케이스 실패

풀이 3

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

using namespace std;

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