[BaekJoon][1654] 랜선 자르기

BAEKJOON ONLINE JUDGE

1654 랜선 자르기

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

N개로 만들 수 있는 최대 랜선의 길이를 찾는 이진 탐색 문제

하나의 값을 가지고 N개 이상 만들 수 있으면 그 길이를 max와 비교, max를 갱신 한 후 길이를 늘려서 다시 탐색

N개 보다 적게 만들면 길이를 줄여서 다시 탐색

#include <stdio.h>
 
int k, n;
int line[10000];
int max;
 
void bsearch(long long int start, long long int end)
{
    long long int middle;
    int cnt;
    int i;
 
    while (start <= end) {
        middle = (start + end + 1) / 2;
        cnt = 0;
 
        for (i = 0; i < k; i++) {
            cnt += line[i] / middle;
        }
 
        if (cnt >= n) {
//            if (middle > max)    max = middle;
            max = middle;
            start = middle + 1;
        }
        else end = middle - 1;
    }
}
 
int main()
{
    int i;
    int end = 0;
 
    scanf("%d %d", &k, &n);
 
    for (i = 0; i < k; i++) {
        scanf("%d", &line[i]);
        if (line[i] > end)    end = line[i];
    }
 
    bsearch(0, end);
 
    printf("%d\n", max);
 
    return 0;
}

* 재귀로 탐색하는 경우 반복문보다 함수 호출 시간이 걸리기 때문에 비효율적.

=> 이진 탐색은 반복문으로 구현하자. (필요할 때에만 재귀를 사용하자!)

* 입력값과 출력값이 int 범위에 속하지만 middle을 구하는 과정에서 

int 범위를 넘어가 overflow가 발생할 수 있기 때문에 이를 방지하기 위해 long long ing 형으로 선언

* middle의 값이 start + end가 홀수인 경우 (예를 들어, 1 + 2인 경우 middle은 1) start 쪽으로 계산이 된다.

      위 문제의 경우 답이 0인 경우가 없기 때문에 0이 계산상에 속하면 안된다.

      따라서 이진 탐색을 시작하는 start를 1로 시작을 하거나,

      middle 계산 값이 start 쪽으로 가지 않도록 (start + end + 1) / 2로 계산을 하여야 한다.

* 조건을 만족하는 최대값을 찾는 문제이기 때문에 조건을 만족할 경우 최대값을 저장하였다.

      하지만 이진탐색이 정답으로 수렴을 하는 탐색법이기 때문에 조건을 만족하는 middle 값의 마지막이 찾는 정답이다.

      (탐색을 종료하는 마지막 middle이 조건을 만족하는 값이라는 보장은 없다.)

(없나...?)