[99클럽/코딩테스트 챌린지/C++] 예산 분배 문제에서 이분 탐색을 활용한 최적 상한액 찾기

오늘은 이분 탐색을 활용해 예산 분배 문제를 풀면서 탐색 범위 설정과 조건에 맞는 최적의 상한액을 찾는 방법을 배웠습니다. 특히 제한된 예산 내에서 최대 상한액을 찾는 과정에서 이분 탐색이 효율적이라는 점을 실감했습니다.

문제 링크 : 

https://www.acmicpc.net/problem/2512

문제 접근 과정

1. 상한액 설정과 탐색 범위 설정
   • 주어진 예산을 초과하지 않으면서 지방의 요청 예산을 최대한 배정해야 합니다. 이를 위해 특정 상한액 이하의 요청은 그대로 배정하고, 상한액을 초과하는 요청은 상한액만 배정합니다.
   • 탐색 범위는 low = 1부터 high = 가장 큰 요청 금액까지 설정합니다. 상한액을 이 범위 내에서 조정해 최적의 값을 찾아야 합니다.
2. 이분 탐색을 통한 최적 상한액 찾기
   • 이분 탐색을 사용해 상한액을 mid로 설정하고, mid를 기준으로 예산 배정을 시뮬레이션합니다.
   • sum 변수를 사용해 각 요청 금액에 대해 상한액(mid)을 적용하여 총 예산 사용액을 계산합니다. 예산 사용액이 총 예산(M)을 넘으면 탐색 범위를 줄이고, 그렇지 않으면 상한액을 증가시켜 탐색을 계속합니다.
3. 조건에 따른 탐색 범위 조정
   • 만약 예산 사용액이 M보다 작거나 같다면 low를 mid + 1로 늘려 더 큰 상한액을 탐색합니다. 이때, result에 현재 mid 값을 저장하여 최적의 상한액을 갱신합니다.
   • 예산 사용액이 M보다 크면 상한액을 줄여야 하므로 high를 mid - 1로 조정합니다.

코드 풀이

아래는 문제 해결을 위한 최종 코드입니다:

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N = 0;

    std::cin >> N;
    vector<int> map(N);
    long long M = 0;
    for(int i = 0; i < N; i++)
    {
        std::cin >> map[i];
    }
    std::cin >> M;

    sort(map.begin(), map.end());

    long long low = 1;
    long long high = map[map.size() - 1];
    long long result = 0;
    while(low <= high)
    {
        long long mid = (low + high) / 2;
        long long sum = 0;

        for(int i = 0; i < map.size(); i++)
        {
            sum += mid < map[i] ? mid : map[i];
            // 이미 합산이 총액보다 클경우 종료
            if (sum > M) break;
        }

        // 총액보다 작을 경우
        if(sum <= M)
        {
            result = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }

    std::cout << result << std::endl;
    return 0;
}

배운 점과 결론

이번 문제를 통해 탐색 범위를 설정하고 조건에 맞는 최적의 상한액을 찾는 방법을 배울 수 있었습니다.

1. 이분 탐색을 활용한 최적값 찾기 : 상한액과 같은 최적의 값을 찾는 문제는 이분 탐색을 통해 효율적으로 해결할 수 있음을 깨달았습니다. 탐색 범위를 반으로 줄여가며 예산 내에서 가능한 최대 상한액을 찾아냈습니다.
2. 조건 기반 반복문 조기 종료 : 예산을 초과하는 경우 조기 종료하는 조건을 추가하여 계산을 효율화할 수 있었습니다. 큰 입력을 다룰 때 불필요한 연산을 줄이는 것이 성능에 얼마나 중요한지 확인할 수 있었습니다.
3. 탐색 범위 설정의 중요성 : low와 high를 설정할 때, high를 가장 큰 요청 금액으로 설정하여 상한액 탐색 범위를 줄였습니다. 탐색 범위를 최적으로 설정하는 것이 문제 해결에 큰 영향을 미친다는 것을 다시 한번 느꼈습니다.

결론

이번 문제를 통해 최적의 상한액을 이분 탐색으로 찾는 방법을 익혔습니다. 앞으로도 탐색 범위를 설정하고 조건에 맞춰 효율적으로 탐색할 수 있도록 훈련을 계속해야겠다고 생각했습니다.