(매일 BOJ) C++ 2512번 예산

이번 문제는 2512번 예산 문제이다.

접근법

이 문제의 알고리즘 분류를 까보면 이분탐색 활용해야 한다고 작성되어 있다. 

 

따라서

start 값은 1,

end 값은 예산 요청에서 가장 큰 값

으로 설정한 후 for문 안에서 sum 변수를 만들어 start와 end값을 기준으로 생성된

1) mid값보다 작으면 예산값을 더하고

2) mid값보다 크면  mid 값을 더하는 방식으로 처리했다.

 

이분탐색

# 핵심 개념

• 정렬된 배열에서만 사용할 수 있음 (오름차순/내림차순 모두 가능)
• 탐색 범위를 반으로 줄여가며 원하는 값을 찾음
• 중간값(mid)을 기준으로 원하는 값이 왼쪽에 있는지, 오른쪽에 있는지를 판단

# 기본 구조

int binary_search(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) return mid;       // 찾은 경우
        else if (arr[mid] < target) left = mid + 1; // 오른쪽 절반 탐색
        else right = mid - 1;                      // 왼쪽 절반 탐색
    }

    return -1; // 못 찾은 경우
}

 

# 시각화

배열:       [10, 20, 30, 40, 50, 60]
인덱스:       0   1   2   3   4   5
찾고 싶은 값: 40

1단계: mid = 2 → arr[2] = 30 → 40 > 30 → 오른쪽 탐색 (left = 3)
2단계: mid = 4 → arr[4] = 50 → 40 < 50 → 왼쪽 탐색 (right = 3)
3단계: mid = 3 → arr[3] = 40 → 찾았다!

# 주의사항

• 정렬되어 있지 않으면 사용할 수 없음
• 오버플로우 방지: mid = left + (right - left) / 2;를 쓰는 경우도 있음
• start <= end 조건 또는 start < end 조건은 문제 유형에 따라 달라짐

 

작성코드

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<int> v;

    for (int i = 0; i < n; i++){
        int money;
        cin >> money; // 지방 예산 요청
        v.push_back(money);
    }

    int max;
    cin >> max; // 총예산
    sort(v.begin(),v.end());

    int start = 1;
    int end = v.back();

    int result;

    while(start <= end){
        int mid = (start + end)/2;
        int sum = 0;

        for(int i  = 0; i < v.size(); i++){
            if (v[i] <= mid) sum += v[i];
            else sum += mid;
        }
        if (sum > max) end = mid - 1;
        else{
            if (mid <= end){
                result = mid;
            }
            start = mid + 1;
        }
        
    }
    cout << result;
}