[프로그래머스] 예산, 쉽게 생각하면 쉬운 문제

예산

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

완전탐색 문제인지 알았다. 조합을 통해서 요소들의 합이 budget보다 같거나 작을 때 가장 개수가 많은 방식으로 접근했다. 그러나 시간 효율성을 통과하지 못했고, 그 결과 깊은 고민에 빠졌다.

문제를 어렵게 생각하니 풀이도 어려웠다. 프로그래머스 1단계 문제 중 가장 오랫동안 고민했다. 답은 너무나도 쉬웠다. 혹시나 해봐서 했더니 되었다. 그냥 주어진 배열을 오름차순으로 정렬한 뒤 앞에서부터 차례대로 더해간 뒤 budget 값보다 크면 지금까지 더한 개수를 반환하면 된다... 수학적으로도 맞는 접근이다...

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> d, int budget)
{
    int count = 0;
    int sum = 0;
    sort(d.begin(), d.end());

    for(int num : d)
    {
        sum += num;

        if(sum <= budget)
        {
            count++;
        }
        else
        {
            break;
        }
    }

    return count;
}

---

2018/12/19 - [프로그래머스] 소수의 합, 소수 판별 알고리즘

2018/12/21 - [프로그래머스] 완주하지 못한 선수, map과 unordered_map의 차이

2018/12/23 - [프로그래머스] N으로 표현

2018/12/23 - [프로그래머스] 모의고사

2018/12/23 - [프로그래머스] K번째수, vector.assign()

2018/12/25 - [프로그래머스] 체육복, 벡터 삭제 시 주의점 (iterator, erase)

2018/12/26 - [프로그래머스] 가운데 글자 가져오기, 짝수 홀수 판별 알고리즘