[백준][BOJ 2805] - 나무 자르기

문제

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

2805번: 나무 자르기

 

 

문제 접근

• $N$과 $M$이 매우 크기 때문에 일반적인 완전탐색 알고리즘으로는 해결할 수 없다. 따라서 다른 방식을 찾아야 한다.
  • 적어도 $O(logN)$이 되어야 할 것이다.
• 적어도 M미터의 나무를 가져가야 하는데 목재 절단기의 높이 $H$를 이분 탐색으로 확인할 수 있다. 가져가려하는 나무의 길이 M은 모든 나무의 높이 합까지 될 수 있기 때문에 절단기가 가질 수 있는 높이는 0부터 시작해야 한다.
• 또한 절단기의 높이의 상한선은 나무들의 모임 중 가장 큰 나무의 높이가 될 것이다. 따라서 절단기의 높이 범위는 $0 \leq H \leq \max(tree)$가 될 것이다.
• 목재의 계산은 문제에 제시된 대로 따라하면 구할 수 있다. 이때 목재가 목표량 $M$보다 크거나 같다면 더 높은 위치에서 잘라도 목재가 $M$이 될 수 있기 때문에 하한을 높이면 된다. 그 반대라면 더 낮은 높이에서 잘라야 하므로 상한을 낮추면 된다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    int[] trees = new int[N];

    long start = 0;
    long end = 0;

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++){
      trees[i] = Integer.parseInt(st.nextToken());
      end = Math.max(end, trees[i]);
    }

    while(start < end){
      long mid = (start + end) / 2;

      if (cut(mid, trees) >= M){
        start = mid + 1;
      } else{
        end = mid;
      }
    }

    System.out.println(start - 1);
  }

  public static long cut(long cutHeight, int[] trees){
    long cnt = 0;

    for (int tree : trees) {
      if (tree > cutHeight) {
        cnt += tree - cutHeight;
      }
    }

    return cnt;
  }
}

• 해당 문제 유형은 upper bound, lower bound로 대표되는 이분 탐색의 상계, 하계를 묻는 유형인데 아직 이해가 잘 되지 않아 추가적으로 공부가 필요하다.