1654, Silver 3

1654번: 랜선 자르기

문제

• $k(1 \leq k \leq 10^{4})$개의 랜선을 정수크기로 잘라 같은 길이의 $n(1\leq n \leq 10^{6})$개의 랜선을 사용한다
• 사용할 수 있는 가장 긴 랜선의 길이는?

 

$O(k\cdot log\ n)$

사용할 수 있는 랜선의 길이가 $hight$라고 가정하고 가능한지 불가능한지 판단한다. 
각 랜선을 $hight$으로 나눴을 때 몫의 합이 $n$ 이상인지 판단하면 된다 $O(k)$

이분탐색을 이용하여 $hight$을 찾는다 

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
typedef long long ll;
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    ll k, n;
    cin >> k >> n;
 
    vector<int> lan(k);
 
    ll lo = 1, hi = 1;
    for(auto& e: lan) {
        cin >> e;
        if(e > hi) hi = e;
    }
 
    ll res = -1;
    while(lo <= hi){
        ll mid = (lo + hi)/2;
        ll cnt = 0;
        for(auto e: lan) cnt += e/mid;
        if(cnt >= n){
            res = mid;
            lo = mid + 1;
        }
        else hi = mid - 1;
    }
 
    cout << res << endl;
 
    return 0;
}cs

※ long long 을 사용할 때는 다른 문자들도 int 가 아닌 long long 사용하자