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

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

 

길이가 제각각인 K개의 랜선을 특정한 길이로 일정하게 잘라 N개로 만들기

가능한 길이 중 가장 긴 것을 찾아야 하므로, 1부터 최댓값 내에서 이분탐색으로 찾는다.

자료형 int 썼다가 틀렸습니다 떴는데 long long으로 바꿔서 성공...

 

이분 탐색 코드

전체 개수가 n개보다 같거나 커져야 하므로 cnt 변수를 만들어 탐색한다.

가능한 길이를 찾았을 때 answer 변수에 mid값을 저장해주는 것도 까먹지 말기

int binSearch(int k, int n, vector<long long>&arr) {
    long long left = 1;
    long long right = arr[k-1];
    int answer = 0;
    
    while(left<=right){
        long long mid = (left + right)/2;
        int cnt = 0;
        for(int i=0;i<k;i++){
            cnt += arr[i] / mid;
        }
        if(cnt >= n){ //n개보다 많이 만들어도 ok
            //해당 길이로 자를 수 있음 -> 더 긴 걸로 다시 시도 (오른쪽으로 탐색)
            answer = mid;
            left = mid+1;
        } else {
            right = mid-1; //왼쪽으로 탐색
        }
    }
    return answer;
}

 

전체 코드

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

using namespace std;

int binSearch(int k, int n, vector<long long>&arr) {
    long long left = 1;
    long long right = arr[k-1];
    int answer = 0;
    
    while(left<=right){
        long long mid = (left + right)/2;
        int cnt = 0;
        for(int i=0;i<k;i++){
            cnt += arr[i] / mid;
        }
        if(cnt >= n){ //n개보다 많이 만들어도 ok
            //해당 길이로 자를 수 있음 -> 더 긴 걸로 다시 시도 (오른쪽으로 탐색)
            answer = mid;
            left = mid+1;
        } else {
            right = mid-1; //왼쪽으로 탐색
        }
    }
    return answer;
}

int main()
{
    int k, n;
    cin >> k >> n;
    vector<long long> arr(k);
    for(int i=0;i<k;i++){
        cin>>arr[i];
    }
    sort(arr.begin(), arr.end());
    int answer = binSearch(k, n, arr);
    cout << answer;
    return 0;
}