[백준][1654번][이분탐색] 랜선 자르기

랜선자르기

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

<코드>

#include <stdio.h>
#include <climits>
int main(void){
    int N, K;
    long long lan[10001] = {};
    long long max = 0;
    scanf("%d %d", &K, &N);
    
    for (int i = 0; i < K; i++)
        scanf("%lld", &lan[i]);
 
    long long left = 0;
    long long right = LLONG_MAX;
 
    while (left <= right){
        long long mid = (left + right) / 2;
        int result=0;
 
        for (int i = 0; i < K; i++)
            result += lan[i] / mid;
 
        if (result >= N)
        {
            left = mid + 1;
            if (mid > max)
                max = mid;
        }
        else
            right = mid - 1;
 
    }
 
    printf("%lld\n", max);
 
 
    return 0;
}

<문제 푼 요령>

1. 이분 탐색 같은 경우는 답을 유추해서 문제에 대입 정답을 도출하는 경우가 많다. 

2. 이 문제도 길이에 대한 정답을 도출해서 2분 탐색으로 끊임없이 탐색해서 결론을 도출하는 것이다. 즉 길이를 정하고 그 길이에 대한 값으로 랜선을 잘랐을시 그 개수가 원하는 개수보다 크거나 같으면 left를 mid+1 로 반대면 right를 mid-1로 바꾸는 것이다.

3. 여기서 범위가 int로 하니까 오류가 났다. 그래서 long long 으로 해줘서 정답을 도출 하였다.