예산 C++(이분탐색)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산 | 프로그래머스

 

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.

1.모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.   2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다.

 

문제!!

각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

지방의 수는 3 이상 100,000 이하인 자연수입니다. 각 지방에서 요청하는 예산은 1 이상 100,000 이하인 자연수입니다. 총 예산은 지방의 수 이상 1,000,000,000 이하인 자연수입니다.

예시

budgets	M	return
{ 120, 110, 140, 150 }	485	127
{ 1,2,3,4,5,6,7,8,9,10 }	56	10

 

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다.

 

---

2. 문제풀이

저는 상한액을 이용하여 이분탐색을 했습니다. 예산은 1이상 100,000 이하입니다. 따라서 최솟값(min)을 1로 잡고 최댓값(max)을 100,000으로 잡은뒤에 계산을 시작합니다.   최솟값과 최댓값의 평균(avg)을 이용하여 비교를 하는데 이 평균(상한액)보다 지방에서 요청하는 예산이 크다면 상한액을 sum에 더하고 평균 보다 작다면 요청한 값을 sum에 모두 더합니다. # 상한액에 한번도 걸리지 않고 총합이 최대예산보다 적다면 지방이 요청한 예산중 최댓값을 리턴합니다.   모든 예산을 더한값이 최대 예산을 넘었다면 최댓값을 평균값(avg)-1로 변경후 위 사항을 반복합니다. 모든 예산을 더한값이 최대 예산을 넘지 않았다면 최솟값을 평균값(avg)+1로 변경후 위 사항을 반복합니다. 반복하기전에 answer에 평균값(avg)으로 항상 갱신시켜 줍니다. 모든 반복문 최솟값(min)이 최댓값하고 같아지거나 커질때까지(=<) 반복합니다.   반복문을 탈출했다면 answer에 최종 상한액이 담기게 됩니다.

 

---

3. 소스코드

3.1 주석없는 코드

#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> budgets, int M) {
    int answer = 0, max = 100000, min = 1, avg;
    while (min <= max) {
        bool check = true;
        long long sum = 0;
        avg = (max + min) / 2;
        for (auto a : budgets) {
            if (a > avg) {
                sum += avg;
                check = false;
            }
            else    sum += a;
        }
        if (sum > M)    max = avg - 1;
        else {
            if (check)        return *max_element(budgets.begin(), budgets.end());
            min = avg + 1;
            answer = avg;
        }
    }
    return answer;
}

3.2 주석있는 코드

#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> budgets, int M) {
    //정답, 최대값, 최솟값, 평균
    int answer = 0, max = 100000, min = 1, avg;
    while (min <= max) {
        //상한액을 정할필요가 없는지 체크용
        bool check = true;
        long long sum = 0;
        avg = (max + min) / 2;
        //순회를 하면서 상한액보다 크다면 평균값으로 바꾸고 저장
        for (auto a : budgets) {
            if (a > avg) {
                sum += avg;
                check = false;
            }
            else    sum += a;
        }
        //총합이 최대 예산을 넘었다면 최대값을 수정하고 다시 반복
        if (sum > M)    max = avg - 1;
        //총합이 최대 예산이 보다 적을때
        else {
            //상한액에 한번도 걸리지않았다면 원소중 최댓값 리턴
            if (check)        return *max_element(budgets.begin(), budgets.end());
            //그게아니라면 최솟값 바꾸고 다시계산
            min = avg + 1;
            answer = avg;
        }
    }
    return answer;
}

3.3 테스트 코드 추가

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> budgets, int M) {
    //정답, 최대값, 최솟값, 평균
    int answer = 0, max = 100000, min = 1, avg;
    while (min <= max) {
        //상한액을 정할필요가 없는지 체크용
        bool check = true;
        long long sum = 0;
        avg = (max + min) / 2;
        //순회를 하면서 상한액보다 크다면 평균값으로 바꾸고 저장
        for (auto a : budgets) {
            if (a > avg) {
                sum += avg;
                check = false;
            }
            else    sum += a;
        }
        //총합이 최대 예산을 넘었다면 최대값을 수정하고 다시 반복
        if (sum > M)    max = avg - 1;
        //총합이 최대 예산이 보다 적을때
        else {
            //상한액에 한번도 걸리지않았다면 원소중 최댓값 리턴
            if (check)        return *max_element(budgets.begin(), budgets.end());
            //그게아니라면 최솟값 바꾸고 다시계산
            min = avg + 1;
            answer = avg;
        }
    }
    return answer;
}
 
void print(vector<int> budgets, int M, int answer){
    int t = solution(budgets, M);
    if (t == answer)    cout << "정답" << endl;
    else    cout << "틀림" << endl;
}
 
int main() {
    print({ 120, 110, 140, 150 }, 485, 127);
    print({ 1,2,3,4,5,6,7,8,9,10 }, 56, 10);
    return 0;
}

---

4. 결과