[C++] BOJ (백준) 1654 : 랜선 자르기

문제

1654번: 랜선 자르기 (acmicpc.net)

1654번: 랜선 자르기

코드

#include <iostream>
#include <vector>

using namespace std;

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

    int k, n;
    cin >> k >> n;
    vector<int> v(k);
    int high = 0;

    for (int &i : v) {
        cin >> i;
        high = max(high, i);
    }

    long long low = 1;
    int res = 0;

    while (low <= high) {
        long long mid = (low + high) / 2;
        int cnt = 0;

        for (int i : v) cnt += i / mid;

        if (cnt >= n) {
            low = mid + 1;
            if (mid > res) res = mid;
        } else {
            high = mid - 1;
        }
    }

    cout << res;
    return 0;
}

설명

답의 최댓값은 주어지는 막대의 길이 중 가장 큰 값이므로 v의 최댓값을 high 변수에 저장한다.
그 후,  1부터 high까지 이분탐색으로 n개의 랜선을 만들 수 있는 경우 중 가장 길이가 긴 경우를 출력한다.
주어지는 막대의 길이의 입력 최댓값이 2147483647(int의 최댓값)이므로
mid 의 값을 long long (int)형 변수에 담았다.