[백준] 1654 랜선 자르기 c++

 

가장 긴 랜선을 기준으로 1부터 가장 긴 랜선 길이를 탐색하면서 갯수가 k이상이 되게 하는 값 중 최댓값을 구하는 문제이다. 

주의할 점은, 완전탐색을 할 경우 1,000,000 *10,000의 시간복잡도가 나오기 때문에 1부터 가장 긴 랜선의 길이를 탐색할 때, 이진탐색을 이용해야 한다. 

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int n, k;
vector<int> v;
long long answer;
//갯수 합산하는 함수
int check(int num) { 
    int result = 0; //랜선 조각 갯수
    for (int i = 0; i < v.size(); i++) {
        result += v[i] / num;
    }
    return result;
}
int main()
{
    cin >> n >> k;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    
    long long start = 1;
    long long end = v[n - 1];
    long long result = 0;
    
    while (start <= end) {
        long long mid = (start + end) / 2;
        
 
        if (check(mid) >= k) { //조각보다 많으면 위로 올라가면서 최댓값 찾기
            answer = max(answer, mid);
            start = mid + 1;
        }
        else { //조각보다 적으면 아래로 내려가기
            end = mid - 1;
        }
    }
    cout << answer;
 
}