백준 2805 나무 자르기 (Java)

1. 문제 링크

2805번: 나무 자르기

 

2. 문제 및 입출력예제

 

3. 문제 풀이

나무 높이 범위가 매우 커서 이분탐색으로 풀었다.

최댓값과 자른 값의 중간 값을 이용해 중간값보다 큰 나무에서 그만큼 베어간다.

자른 나무의 합이 원하는 값인 M보다 작으면 높이를 낮춰야 하니까 현재 최댓값을 중간값으로 넣고 반복한다.

만약 자른 나무의 합이 M보다 크거나 같아지면 중간값보다 하나 큰 값을 넣고 반복한다.

 

뭔가 하나씩 풀어쓰려니까 애매한데

자른 값이 모자라면 자르는 높이를 낮추고, 자른 값이 넘치면 자르는 높이를 높이면서 값을 찾는다.

 

4. 코드

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

public class Main {
	
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		String[] nm = br.readLine().split(" ");
		int N = Integer.parseInt(nm[0]);
		int M = Integer.parseInt(nm[1]);
		
		int use = 0;
		int max = 0;
		int[] tree = new int[N];
		String[] split = br.readLine().split(" ");
		for(int i=0;i<N;i++) {
			tree[i] = Integer.parseInt(split[i]);
			max = Math.max(max, tree[i]);
		}
		while(use < max) {
			int mid = (use + max) /2;
			long sum = 0;
			for(int h: tree) {
				if(h-mid>0) {
					sum+=h-mid;
				}
			}
			if(sum < M) {
				max = mid;
			}
			else {
				use = mid + 1;
			}
		}
		
		System.out.println(use-1);
	}
}