Programmers: 예산

문제

• https://programmers.co.kr/learn/courses/30/lessons/12982
• 분류: 그리디

문제 설명

• 최대한 많은 부서를 지원하려고 하는데 몇개의 부서에 지원이 가능한가?
• 그냥 예산 적게 요청하는 부서부터 차례로 지원하면 결국 최대한 많은 부서 지원 가능이 됨

알고리즘

• 부서 예산 리스트를 정렬한다
• 부서 리스트를 돌면서
  • 각 부서에서 사용하는 예산 + 현재 총 사용한 예산 <= 쓸 수 있는 총 예산 이면
  • 현재 총 사용한 예산 += 각 부서에서 사용하는 예산 업데이트
  • 그리고 부서 카운트 증가
• 끝![전형적이고 기본적인 그리디 알고리즘!]

코드

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

using namespace std;

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

    for (int i = 0; i < d.size(); i++) {
        if (d[i] + sum <= budget) {
            sum += d[i];
            counter++;
        }
    }
    return counter;
}