(매일 BOJ) C++ 1654번 랜선 자르기

이번 문제는 1654번 랜선 자르기 문제이다.

접근법

가지고 있는 랜선을 잘라 같은 길이의 원하는 개수로 만드는 문제이다. 이 문제에서는 주어진 랜선의 개수가 만개 만들어야 할 랜선의 개수가 최대 100만개 이하로 주어지기에 브루트포스를 사용한다면 TLE 가 발생하는 것을 볼 수 있다.

따라서 랜선의 최소 길이를 1, 최대 길이를 가장 긴 랜선으로 설정한 후 길이를 이분탐색을 사용하여 찾아내면 TLE가 발생하지 않고 원하는 값을 찾아내는 것을 볼 수 있을 것이다.

추가적으로 이 문제에서는 랜선의 최대 길이가 2의 32승 -1 까지이기에 길이와 관련된 변수들을 long long으로 설정해야 함을 주의해야 한다.

작성코드

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int have_len, need_len;
    cin >> have_len >> need_len;
    vector<long long> v;
    for(int i = 0; i < have_len; i++){
        long long num;
        cin >> num;
        v.push_back(num);
    }

    sort(v.begin(),v.end());
    long long start = 1, end = v.back();
    long long answer = 0;

    while(start <= end){
        long long mid = (start + end) / 2;
        long long count = 0;

        for(int j = 0; j < v.size(); j++){
            count += v[j] / mid;
        }

        if(count >= need_len){
            answer = mid;
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
    }
    cout << answer;
}