백준 1654 랜선 자르기

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> lan;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int k, n;
    int m = 0;

    cin >> k >> n;

    lan.resize(k);



    for (int i = 0; i < k; i++) {
        cin >> lan[i];
        m = max(m, lan[i]);
    }


    long long l = 1;
    long long r = m;
    long long ans = (l + r) / 2;

    while (l <= r) {
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            cnt += lan[i] / ans;
        }

        if (cnt >= n) {
            l = ans + 1;
        } else {
            r = ans - 1;
        }
        ans = (l + r) / 2;
    }

    cout << ans << "\n";


    return 0;
}

 

  이분 탐색 문제이다.

 숫자의 범위가 매우 크므로 일반적인 탐색으로 풀면 시간 초과가 난다. 따라서 이분 탐색을 이용해 문제를 푼다.

 

풀이 

    long long l = 1;
    long long r = m;
    long long ans = (l + r) / 2;

    while (l <= r) {
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            cnt += lan[i] / ans;
        }

        if (cnt >= n) {
            l = ans + 1;
        } else {
            r = ans - 1;
        }
        ans = (l + r) / 2;
    }

 

  랜선의 길이는 주어진 길이 중 가장 긴 랜선을 넘어갈 수 없으므로 1부터 최댓값 중 이분 탐색을 수행한다. 주어진 랜선을 ans라는 동일한 길이로 잘라 n을 만드는 것이 목표이므로 cnt에 랜선을 ans의 길이로 잘랐을 때 나오는 랜선의 수를 계산한다. 이분 탐색을 통해 n을 찾고, 그 때의 길이 ans를 출력하면 정답을 구할 수 있다.