[알고리즘] 백준 18113번: 그르다 김가놈 (C++)

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

18113번: 그르다 김가놈

해석만 잘 되면 쉬운 문제였다. 이분 탐색이 필요했던 이유는 k의 범위가 1~10^9까지 가질 수 있었기 때문에 O(N)으로 하면 시간 초과가 나서 이분 탐색인 O(logN)으로 풀어야 한다.

#include <iostream>
#include <vector>
using namespace std;

int n, k, m;
vector<int> v;

int main(){
    cin >> n >> k >> m;
    
    for(int i = 0; i < n; i++){
        int len;
        cin >> len;
        v.push_back(len);
    }
    
    int low = 1;
    int high = 1000000000;
    int result = -1;
    
    while(low <= high){
        int mid = (low + high) >> 1;
        
        int cnt = 0;
        for(int i = 0; i < v.size(); i++){
            if(v[i] <= k) continue;
            if(v[i] >= 2 * k) {
                cnt += (v[i] - 2 * k) / mid;
            }
            else{
                cnt += (v[i] - k) / mid;
            }
        }
        
        if(cnt >= m){
            low = mid + 1;
            result = mid;
        }
        else{
            high = mid - 1;
        }
    }
    
    cout << result;
    return 0;
}