[백준] 2805 나무 자르기

문제

실버2 문제

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

문제 해설

이분탐색의 개념을 응용한 문제로 쉬운 편이다.
나무의 수 N
가져갈려는 나무의 길이 M
주어졌을때
이분탐색의 개념을 적용하면
low = 0부터 High를 가장 큰 나무로 설정하고
mid = 가장 큰 나무의 중앙값을 구하고
배열의 요소를 하나씩 mid로 나눠 남은 나무의 길이를 합한다
합한 값이 가져갈려는 나무의 길이 M과 같거나 클 경우
mid의 값을 출력하면 된다.

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static ArrayList<Integer> arr_int = null;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		arr_int = new ArrayList<Integer>();
		
		for(int i = 0; i < N; i++) {
			
			int number = sc.nextInt();
			
			arr_int.add(number);
		}
		
		int max = 0;
		
		for(int i : arr_int) {
		
			max = Math.max(max, i);
		}
		
		System.out.println(binary(M,max));
		
	}

	public static long binary(int M, int max) {
		
		int start = 0;
		int end = max + 1;
		
		while(start < end) {
			
			int mid = (start + end) / 2;
			long sum = 0;
			
			for(int i : arr_int) {
				
				//절단한 나무의 길이를 저장
				if(i - mid > 0) {
					
					sum += i - mid;
				}
			}
			
			if(sum < M) {
				
				end = mid;
			}
			
			else {
				start = mid + 1;
			}
			
		}
		
		return start-1;
	}
}