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

1. 문제 개요

https://programmers.co.kr/learn/courses/30/lessons/12982?language=cpp

코딩테스트 연습 - 예산

 1-1. 설명

각 부서에 필요한 물품을 지원해주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사한다. 전체 예산이 정해져 있으므로, 모든 부서에 물품을 구매할 수 없다. 그래서 최대한 많은 부서의 물품을 구매할 수 있도록 한다. 부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최 대 몇개의 부서에 물품을 지원할 수 있는지 return 하도록 함수를 완성한다. 

 

 1-2. 제한 사항

- d의 길이는 1이상 100이하

- d의 각 원소는 부서별 신청 금액이며, 1이상 100,000이하의 자연수

- budget은 예산을 나타내며, 1이상 10,000,000이하의 자연수

 

---

2. 구현

2-1. 풀이

신청한 금액중 가장 적은 금액을 우선순위로 구매하면 최대한 많은 부서에 지원해줄 수 있다고 생각하여 벡터 d를 먼저 sort해주었다. 그리고 반복문을 돌려 예산이 0 미만이 될 때까지 빼주었다. 

 

2-2. 코드

#include <vector>
#include <algorithm>
using namespace std;

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