[프로그래머스] 예산 (C++)

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

코딩테스트 연습 - 예산

[프로그래머스] 예산 (C++)

 

#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> tmpD=d;
    
    sort(tmpD.begin(),tmpD.end());

    int sum=0;
    for(int i=0;i<tmpD.size();i++) {
        if(sum+tmpD[i]<=budget) {
            sum+=tmpD[i];
            answer=i+1;
        }
        else {
            break;
        }
    }

    return answer;
}

 

첫 시도(시간 초과)

처음에는 next_permutation()을 써서 풀었으나, 시간 초과로 실패..

 

다음 시도(정답)

오름차순으로 정렬하여 작은 것부터 하나씩 최대한 채워나가는 방식으로 풀었다.

수학적으로도 이 방법이 맞다고 생각하여 풀이 제출!