[C/C++] 백준 #1654 랜선 자르기(이분 탐색)

랜선 자르기 문제는 K개의 랜선이 있을 때, 이 랜선을 적절히 잘라서 같은 길이의 N개의 랜선을 만드는 것입니다.  이 때, 가장 긴 길이의 N개의 랜선을 얻고자 할 때, 그 길이를 출력하는 것입니다.

 

이런 최적화 문제는 길이가 주어지면, K개의 랜선에서 N개의 랜선을 만들 수 있는지 검사하는 것은 어렵지 않다는 것입니다.  그리고 \( a \lt b \)를 만족하는 경우 b 길이가 가능하면 a 길이도 가능해야 문제를 풀 수 있습니다.  역으로 a 길이가 불가능하면 b 길이도 불가능해야 합니다.  그래야 이분 탐색을 이용하여 문제를 풀 수 있습니다.

 

4개의 랜선이 각각 길이가 802, 743, 457, 539 길이로 주어져있고, 이것으로 같은 길이의 11개 랜선을 요구한다고 합니다.  \( K \le N \)이므로, 4개의 랜선의 합을 계산합니다.  합은 2,541이 됩니다.  이 값을 11로 나누면, 231이므로, 232는 절대 불가능한 값이 됩니다.  그러면 이 불가능한 값을 right 값으로 설정합니다.  left 값은 1로 설정하면 최소 길이의 랜선이 되므로 항상 성공합니다. 

 

LAN Cables

 

제가 사용하는 이분 탐색의 핵심은 right 값은 실패한 경우이고, left 값은 성공한 경우입니다.  1과 232의 중간값은 116이 됩니다.  116은 802에서 6개를 만들고, 743에서 6개를 만들고, 457에서 3개를, 539에서 4개를 만들 수 있습니다.  총 19개를 만들 수 있으니 성공입니다.  116은 Left 값으로 갑니다.  이를 반복하면 Left, Right 값이 연이어지게 되는 경우가 생깁니다.  그러면 그때 Left 값이 최대값이 됩니다.

 

이것을 표로 표현하면 다음과 같습니다.

 

	Left	Right
0	1	232
1	116	232
2	197	232
3	197	214
4	197	205
5	197	201
6	199	201
7	200	201

 

즉 7번만에 200이라는 숫자를 찾았습니다.  이 알고리즘은 K개의 랜선에 대해서 해당 길이만큼 나누어야 하므로 매 시행마다 \(O(K)\) 효율을 보입니다.  그래서 전체적인 알고리즘 효율은 \(O(K \log \sum_i a_i)\) 정도가 됩니다.

 

아래는 제가 작성한 소스입니다.  소스는 참고용으로만 봐주세요.

//--------------------------------------------------------------------------
//    baekjoon #1654
//        - by Aubrey Choi
//        - created at 2019-09-25
//--------------------------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, k, c, i, s=0x7fffffff, v[10000], min = 1, max = 1;
    scanf("%d%d",&k,&n);
    for(i=0;i<k;i++)
    {
        scanf("%d",v+i);
        if(max<v[i]) max=v[i];
        if(s>v[i]) s=v[i];
    }
    if(s == max && k == n) { printf("%d\n", max); return 0; }
    min = 1;
    while(min+1<max)
    {
        c=(int)(((long)min+max)/2);
        for(i=0, s=0; i<k; i++) s+=v[i]/c;
        if(s>=n) min=c; else max=c;
    }
    printf("%d\n", min);
}