[C/C++] 백준 #2805 나무 자르기(이분 탐색)

이분 탐색은 단순증가하는 형태의 함수에서 원하는 값을 빠르게 찾는데 사용을 합니다.  시간 복잡도는 $O(\log N)$이 됩니다.  하지만, 어떤 지점을 기준으로 실패와 성공이 갈릴 때, 그 기준점을 찾을 때에도 유용합니다.

 

Tree cutting

 

나무 자르기 문제 역시 이분 탐색을 이용하여 성공할 때 최적값을 찾을 수 있습니다.

 

문제의 링크는 다음과 같습니다.

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

 

코드 설명

1. `readint()` 함수

int readint() {
    int s=0,c;
    for(;;){
        c=getchar();
        if(c<'0'||c>'9') break;
        s=s*10+c-'0';
    }
    return s;
}

- 이 함수는 표준 입력으로부터 정수를 읽어오는 함수입니다. 
- `getchar()`를 통해 하나씩 문자를 읽어오고, 이 문자가 숫자일 경우에만 정수로 변환하여 `s`에 누적합니다.
- 숫자가 아닌 문자가 나올 때 루프를 종료하고, 최종적으로 누적된 정수 `s`를 반환합니다.
- 이 함수는 여러 개의 숫자를 효율적으로 읽기 위해 구현되었습니다.

2. `main()` 함수

int main()
{
    int n, m, f=0, l=0;
    static int v[1000000];
    n=readint(); m=readint();
    for(int i=0;i<n;i++) v[i]=readint(), l=(l<v[i])?v[i]:l;

- `n`은 나무의 수, `m`은 필요한 나무의 양입니다.
- `f`는 톱질 높이의 최저값, `l`은 톱질 높이의 최대값입니다. 처음에는 `f`는 0으로 초기화되고, `l`은 나무의 최대 높이로 설정됩니다.
- `v` 배열은 각 나무의 높이를 저장합니다. 최대 1,000,000개의 나무 높이를 저장할 수 있습니다.
- 루프를 통해 `n`개의 나무 높이를 `v` 배열에 저장하고, 이 중 최대값을 찾아 `l`에 저장합니다.

3. 이진 탐색을 통한 최적 톱질 높이 찾기

    while(f < l-1)
    {
        int c=(f+l)/2, i; long long sum=0;
        for(i=0;i<n && sum<m; i++) sum+=(v[i]>c)?v[i]-c:0;
        if(sum>=m) f=c; else l=c;
    }
    printf("%d\n", f);
}

- `while(f < l-1)` 루프는 이진 탐색을 수행하여 톱질할 최적의 높이 `f`를 찾습니다.
- `c`는 `f`와 `l`의 중간값이며, 현재 시도하는 톱질 높이입니다.
- `sum`은 `c` 높이에서 톱질했을 때 얻을 수 있는 나무의 총량입니다.
- `for` 루프는 각 나무에 대해 `v[i]`가 `c`보다 클 경우, 나무의 높이에서 `c`를 뺀 값을 `sum`에 더합니다.
- `sum`이 필요한 양 `m` 이상이 되면, `f`를 `c`로 설정하여 톱질 높이를 높이고, 그렇지 않으면 `l`을 `c`로 설정하여 톱질 높이를 낮춥니다.
- 최종적으로 최적의 톱질 높이 `f`를 출력합니다.

이 코드는 이분 탐색을 사용하여 최적의 톱질 높이를 효율적으로 찾습니다. $O(n\log h)$의 시간 복잡도를 가지며, `n`은 나무의 수, `h`는 나무의 최대 높이입니다. 이진 탐색을 통해 가능성 있는 톱질 높이를 점진적으로 줄여가며 최적의 해답을 찾아냅니다.

 

제가 작성한 코드입니다.

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

int readint() {int s=0,c; for(;;){c=getchar();if(c<'0'||c>'9')break;s=s*10+c-'0';}return s;}
int main()
{
    int n, m, f=0, l=0;
    static int v[1000000];
    n=readint(); m=readint();
    for(int i=0;i<n;i++) v[i]=readint(), l=(l<v[i])?v[i]:l;
    while(f < l-1)
    {
        int c=(f+l)/2, i; long long sum=0;
        for(i=0;i<n && sum<m; i++) sum+=(v[i]>c)?v[i]-c:0;
        if(sum>=m) f=c; else l=c;
    }
    printf("%d\n", f);
}