/<> 백준 2805번 : 나무 자르기 (C언어)

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

 

 

나무 배열을 따로 정렬할 필요 없이 가장 높은 나무의 높이를 기준으로 시작해서 기준을 하나씩 낮추며 자를 수 있는 나무 높이의 총합을 구하면 됩니다. 그래서 그냥 단순하게 반복문을 중복해서 썼더니 시간 초과...

시간 복잡도가 O(n^2)이면 시간 초과가 뜨므로 O(nlogn)인 이진 탐색을 이용하여 풀었더니 맞았습니다. 기준 높이를 0에서부터 시작하기에 더 직관적입니다.

 

1. 나무 배열을 순서대로 입력받습니다. 이후 가장 높은 나무의 높이를 구합니다.

2. 기준 높이를 0에서 시작하여 이진 탐색을 통해 계속 조정하면서 자른 나무의 총합을 M과 비교합니다.

 

 

<코드>

#include <stdio.h>

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int max = 0;
    int tree[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &tree[i]);
        if (max < tree[i]) max = tree[i];
    }

    int low = 0, high = max;
    int result = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            if (tree[i] > mid) sum += tree[i] - mid;
        }
        if (sum >= m) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    printf("%d\n", result);
    return 0;
}

 

 

sum의 자료형을 long long int로 정의한 것을 볼 수 있는데, 1 ≤ M ≤ 2,000,000,000 이므로 int 자료형의 범위를 벗어날 수 있기 때문입니다. 이에 주의합시다.