[C++] BAEKJOON 1654 랜선 자르기

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

1654번: 랜선 자르기

이분탐색 을 이용하여 문제를 해결하였습니다.

이분탐색을 사용하지 않을 시

이분탐색을 사용하지 않은 오답부터 확인해보겠습니다.

자를 랜선의 길이가 1 일 때 부터 보유하고 있는 랜선 중 최대 길이가 될 때 까지 하나씩 확인하여 개수가 N 개 이상이 되는 경우를 찾아줍니다. 이 경우, 시간복잡도를 살펴보면 랜선의 길이가 1부터 최대 랜선의 길이까지 순회하므로 O(2^31) , 보유하고 있는 랜선의 개수만큼 순회하며 총 몇 개가 만들어지는지 확인하므로 O(K) (1<=k<=10,000) 이므로 시간초과 가 발생합니다.

#include <iostream>

using namespace std;

int lan[100000];

int main(int argc, const char * argv[]) {
    
    int K,N;
    cin >> K >> N;
    
    int maxlan = 0;
    
    for (int i=0;i<K;i++){
        cin >> lan[i];
        if (lan[i] > maxlan)
            maxlan = lan[i];
    }
    
    int maxLength = 0;
    
    for (int length=1;length<maxlan;length++){
        int count = 0;
        for (int i=0;i<K;i++){
            count += lan[i] / length;
            if (count >= N) break;
        }
        if (count >= N){
            maxLength = max(maxLength, length);
        }
    }
    
    cout << maxLength << "\n";
    
    return 0;
}

 

이분탐색을 사용할 시

따라서 이분탐색을 이용하여 시간을 줄일 수 있습니다.

자를 랜선의 길이를 1부터 보유하는 최대 랜선의 길이까지 전부 확인하지 않고 이분탐색을 이용해 확인하게 됩니다. 해당하는 랜선의 길이로 잘랐을 때 N 개보다 더 나왔다면, 길이를 증가시키고, N개보다 적게 나왔다면 길이를 감소시켜가며 탐색을 하게 됩니다.

자료형을 신경쓰지 못해서 틀렸는데, 각 랜선의 길이는 2^31-1 이하의 수로 int 자료형으로 표현할 수 있지만,

long long mid=(right+left)/2;

이분 탐색을 수행하기 위해 중간 지점을 찾는 과정에서 두 수를 더하는 순간, 범위를 벗어나는 경우가 생깁니다. 따라서 long long 으로 선언해줘야 합니다.

#include <iostream>

using namespace std;

int lan[10000];

int main(int argc, const char * argv[]) {

    int K,N;
    cin >> K >> N;

    long long maxlan = 0LL;

    for (int i=0;i<K;i++){
        cin >> lan[i];
        if (lan[i] > maxlan)
            maxlan = lan[i];
    }

    long long left = 1LL;
    long long right = maxlan;

    int answer = 0;

    while (left<=right){
        long long mid=(right+left)/2;

        long long count = 0LL;

        for (int i=0;i<K;i++){
            count += lan[i] / mid;
        }

        if (count >= N){
            answer = mid;
            left = mid+1;
        }
        else {
            right = mid-1;
        }
    }

    cout << answer << "\n";

    return 0;
}