[algorithm | 백준/C] 2805: 나무 자르기

 문제 

---

 문제 정의 

문제를 찬찬히 읽어보면.. 나무가 필요한 상근이는 절단기의 높이를 적절히 정해서 나무를 자르고 잘린 부분을 가져간다.

이런 느낌이라고 이해하면 될 거 같다. 직접 그렸다. 이때 상근이가 필요한 만큼(M)만 가져갈 수 있는 절단기의 최대 높이(H)를 구하는 문제이다.

예를 들어 각각 25, 15, 10, 17미터인 4개의 나무가 있고 상근이는 7미터의 나무가 필요하다. 이때 가장 낭비가 없는 절단기의 높이는 15가 된다.

25 - 15 = 5

15 - 15 = 0

10 - 15 = x

17 - 15 = 2

여기서 절단기의 높이가 더 작다면 상근이에게 필요한 나무가 부족하고 절단기의 높이가 더 높다면 낭비되는 나무가 생겨 환경을 생각하는 상근이가 싫어할 것이다.

---

 문제 접근 

절단기 높이 H 를 적절히 정해 잘라낸 나무 길이의 합이 적어도 M 이상이어야하고 이 조건을 만족하는 H의 값 중 H의 최대값이어야 가장 낭비가 없을 것이다.

 

단순히 생각하면 절단기 높이를 최대 나무의 높이까지 하나하나 시도해보고 각 경우마다 잘리는 나무 길이 총합을 계산하면 되지만 브루트포스는 나무 최대 높이가 굉장히 크기때문에 시간초과 때문에 안 된다. 상근이는 바쁘다

 

절단기 높이를 올리면 나무는 줄어들고 절단기 높이를 내리면 잘리는 나무는 많아진다. 이런 단조성이 있는 경우는 계속 반씩 범위를 줄여가는 이분 탐색을 생각해볼 수 있다.

---

 풀이 로직 

먼저 탐색 범위를 정하고 (0부터 가장 높은 나무의 길이) 절단기 높이를 계속 중간값으로 잡아 이 절단기 높이로 잘리는 나무의 길이 합을 구하고 상근이가 필요한 나무 길이 총합 (M)과 비교해 값이 m보다 크면 범위를 오른쪽으로 넓히고 m보다 작다면 왼쪽으로 좁힌다.

---

 코드 - C언어 

#include <stdio.h>

int arr[1000111]; // 최대 나무 높이 저장
int n; // 나무 개수 n, 필요한 나무 길이 m (long long은 큰 수 처리용)
long long m;

int main() {
    long long left = 0; // 이분탐색의 시작점 (절단기 최소 높이)
    long long right = 0; // 이분탐색 끝점 (절단기 최대 높이)
    long long result = 0; // 조건 만족하는 절단기 높이 중 최댓값
    long long max = 0; // 나무 중 가장 높은 나무

    scanf("%d %lld", &n, &m); // 나무 개수와 필요한 나무 길이 입력받기

//나무 높이들을 입력 받고 가장 높은 나무 찾기
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);

        if (arr[i] > max) // 최대 높이
        {
            max = arr[i];
        }
    }

//절단기 최대 높이는 가장 높은 나무 높이
    right = max;
      
//이분 탐색 시작
    while (left <= right) 
    {
        long long mid = (left + right) / 2; //중간값 mid
        long long sum = 0; // 잘라낸 나무 총 길이

// 모든 나무 돌며 mid 높이보다 큰 나무만 잘림
        for (int i = 0; i < n; i++) 
        {
            if (arr[i] > mid) 
            {
                sum += arr[i] - mid; // 자른 나무 길이 합침
            }
        }

// 잘라낸 나무 길이가 필요한 길이보다 많은지 적은지 판단
        if (sum >= m) 
        {
            result = mid;
            left = mid + 1; // 조건 만족하면 더 높아도 되는지 탐색
        }
        else 
        {
            right = mid - 1; // 나무가 부족하니 더 낮게 자르기 위해 작은 값 범위 탐색
        }
    }

    printf("%lld\n", result);

    return 0;
}

처음에 longlong으로 안 하고 바보같이 왜 안되는지 몰랐다..

 해결 

 

해결...!