백준 1654 ( C++ )

랜선 자르기

 

이분 탐색의 응용 버전

 

 

 

문제 풀이

 

  직관적으로 떠오르는 풀이는 가지고 있는 랜선들을 나눈 몫들의 합이 K가 되는 길이를 찾기 위해 길이 1부터 가장 길이가 짧은 랜선 길이까지 반복적으로 랜선들을 나누는 풀이법이다. 정답인 길이가 M 이라면 이 풀이법의 예상 복잡도는 O(NM)이다. 문제에서 N은 1이상 1,000,000 이하의 정수라고 명시했으므로 위 풀이는 시간초과가 발생한다. 그러므로 이분 탐색으로 검색 시간을 N 에서 logN으로 줄여야한다.

 

 

이분 탐색을 어떻게 적용할까?

 

1. left , right 설정

 

 

    이분 탐색을 위해선 인덱스값을 저장할 변수 2개가 필요하다( left, right 혹은 low, high ). 위 문제에서 요구하는 답은 길이이므로 랜선의 최소 길이인 1을 left에, 최대 길이를 가장 긴 랜선의 길이를 right에 저장하자.

 

 

2. left, right 업데이트

 

    그 후 mid 값을 계산하여 mid 값으로 모든 랜선들을 나누었을때 몫들의 합이 K 보다 크거나 같으면 나누는 mid 값이 아직 작은것이므로 left = mid + 1을, 몫들의 합이 K보다 작으면 나누는 mid 값이 아직 큰 것이므로 right = mid - 1를 해준다.

 

 

 

코드

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAX = 10000;
 
int N, K;
 
long long wires[MAX];
 
bool pos(long long len) {
 
    long count = 0;
 
    for (int i = 0; i < N; i++)
        count += wires[i] / len;
 
    if (count >= K) return true;
 
    return false;
}
 
 
int main(void) {
 
    cin >> N >> K;
 
    long max = 0;
 
    for (int i = 0; i < N; i++) {
        long temp;
        cin >> temp;
 
        if (max < temp) max = temp;
 
        wires[i] = temp;
    }
 
    long ans = 0;
    long left = 1;
    long right = max;
 
    while (left <= right) {
 
        long long mid = (left + right) / 2;
 
        if (pos(mid)) {
 
            if (ans < mid)
                ans = mid;
 
            left = mid + 1;
        }
        else
            right = mid - 1;
 
    }
 
    cout << ans << endl;
    return 0;
}

 

 

결과