[BAEKJOON] 2805번 나무 자르기

---

상근이가 필요한 나무의 길이 m을 구할 때까지 절단기의 길이를 늘리거나 줄이는 과정을 반복하여 최대 절단기의 길이를 구하는 문제이다.

절단기의 최소 길이는 0, 최대 길이는 주어진 나무의 최대 길이와 같을 것이다.

(필요한 나무 길이가 주어진 나무의 최대 길이라면 굳이 자를 필요없이 절단기의 길이는 0일 것이고,

필요한 나무 길이가 0일 경우 절단기의 길이는 곧 주어진 나무의 최대 길이가 될 것이기 때문!)

따라서 절단기의 최소 길이 0부터 최대 길이까지 가능한 최대의 절단기 길이를 구한다.

 

절단기의 길이를 0, 1, 2, ... 최대길이까지 반복하기엔 시간과 메모리 초과에 발이 묶일 것이다.

정렬된 상태에서 특정 값을 빠르게 찾기 위해서는 이분 탐색 방법을 사용한다.

위의 그림을 보면 임의로 절단기의 초기 길이를 절단기의 최소길이와 최대길이의 중간값으로 지정했다.

절단 후 절단된 나무들의 길이를 모두 합해서 필요한 나무 길이 m과 같은지 확인한다.

만약 절단된 나무 길이와 필요한 나무 길이 m이 같다면 그 자리에서 반환하고,

절단된 나무 길이가 더 작다 → 절단기의 길이를 늘려야 한다.

절단된 나무 길이가 더 길다  → 절단기의 길이를 줄여야 한다.

 

※ 나무의 길이를 모두 더했을 때 int형 범위를 벗어날 경우가 생길 수 있다! 따라서 long형으로 지정해야 한다.

더했을 때 값을 저장하는 sum, sum과 연산이 이루어지는 나무 길이, 절단기 길이 역시 long형으로 지정해야 한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int n, m;
	static long arr[];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new long[n];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		System.out.println(binary(0, arr[arr.length-1]));
	}
	private static long binary(long start, long end) {
		long mid = (start+end)/2, sum=0;
		if(start>end) return mid;
		for(int i=0; i<n; i++) {
			if(arr[i] > mid) {
				sum += arr[i]-mid;
			}
		}		
		if(sum >= m) return binary(mid+1, end); 
		else return binary(start, mid-1);
	}
}

[출처]

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

2805번: 나무 자르기