Lv1_[예산, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

알고리즘

문제와 풀이 과정을 보면 경우의 수를 구해야하는 것 같고 복잡해보일 수 있지만 잘 보면 간단히 풀리는 문제입니다.

예산을 가지고 최대 몇 개의 부서에게 지원해줄 수 있냐는 것인데

"금액을 적게 요청한 부서에게 순서대로 주었을 때 최대 몇개 부서가 받을 수 있는가?"를 체크하면 됩니다.

• 입력이 들어온 d를 오름차순 정렬해줌
• 순서대로 더하면서 총 합이 budget을 넘는지 체크
• 넘으면 종료 후 값 리턴

정렬 후 합

 

index[3]일 때 budget 크기를 넘기 때문에 최대 3개의 부서에 물품을 지원할 수 있음

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> d, int budget) {
    int answer = 0;
    int sum = 0;
 
    sort(d.begin(), d.end());
    for(int i = 0; i < d.size(); i++) {
        sum += d[i];
        if(sum > budget) {
            break;
        }
        answer++;
    }
 
    return answer;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓