프로그래머스, 예산 : C++ [CPP]

Greed 하게 풀었는데

Greed를 시도해보니 맞았다.

보다는

Greed를 쓴 이유를 알면 좋다.

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

 

---

#맞은 풀이

#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()); // 오름차순 정렬.
    //Greed 방법 적용 -> 가장 적은 부서부터 적용
    for(int x : d){
        if(x<=budget){
            budget -= x;
            answer++;
        }else{
            //신청비용이 더 커버리면 어차피 뒤에 것들은 다 크므로 조사할 필요 x
            break;
        }
    }
    return answer;
}

 

즉, 최대한 많은 부서를 지원하려면 

신청 비용이 작아야 한다.

왜냐하면 budget은 신청 비용만큼 사라지기 때문이다. 

budget 많을수록 부서를 지원할 수 있으므로 신청 비용이 낮은 부서부터 지원하는 것이

budget을 절약하는 방법이다.