백준 #1654 랜선 자르기


BOJ #1654 - 랜선 자르기

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

# 문제 분류

이분 탐색

풀이 접근 방법


이분 탐색을 해주면 된다. 너무 자명하다.


#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, K, length;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> K >> N;

    vl v;
    for (int i = 0; i < K; i++) {
        cin >> length;
        v.emplace_back(length);
    }

    ll l = 0, r = INT32_MAX;
    while (l <= r) {
        ll mid = (l + r) / 2;

        ll cnt = 0;
        for (ll p : v) {
            cnt += p / mid;
        }

        if (cnt >= N) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << l - 1;
}