BOJ - 랜선 자르기(1654)

실버3 : 이분 탐색 문제이다.

생각

이분 탐색 문제이다. 이전의 문제들과 마찬가지로, 값을 제시하고 그에 대한 분기를 만드는 것이 중요하다. 이 때, 어느 영역에서 답이 나오는지를 잘 체크하고, 답의 후보를 기록해두는 행위가 중요하다.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
ll K, N;
ll a[10001];
 
ll f(ll sug){
    ll count = 0;
    for (int i = 0; i < K; i++) {
        count += (a[i]/sug);
    }
    return count;
}
 
int main(){
    cin >> K >> N;
    for (int i = 0; i < K; i++) {
        cin >> a[i];
    }
    sort(a, a+K);
    ll start = 1, end = (1LL << 31)-1, mid = 0, ans = -1;
    while (start <= end) {
        mid = (start+end)/2;
        ll count = f(mid);
 
        if (count < N) {
            end = mid - 1;
        } else {
            ans = max(ans, mid);
            start = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Reference

• 백준(1654번) - 랜선 자르기