[프로그래머스] 1단계 - 예산

문제 설명

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

프로그래머스

주어진 예산안에서 최대한 많은 부서들을 지원하는 수를 구하는 문제 

 

문제 풀이법

가장 많은 부서들을 지원하므로 지원 금액을 작은 순서대로 정렬한 후, 지원 금액을 하나씩 제외해 가면서 예산을 구함

맨 뒤의 수. 즉 가장 큰 지원금을 제외하면서 총 예산이 정해진 예산을 넘지 않으면 그 수가 최대이므로 바로 return 

 

소스 코드

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

using namespace std;

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