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

 

 

 

매개 변수 탐색을 활용해 풀 수 있는 문제이다.

 

알고리즘 분류에 매개 변수 탐색이라고 나와있어서 쉽게 찾을 수 있지만.. 어떤 문제를 매개 변수 탐색으로 풀 수 있는지, 어떤 경우에 매개 변수 탐색이 효율적인지 알아두자.

 

 

매개 변수 탐색을 활용하기 위해 문제를 적절하게 변형하자.

 

 

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구해라.

=>

절단기에 특정 높이를 설정했을 때 적어도 M미터의 나무를 집에 가져갈 수 있는가?

 

 

 

import java.util.*;
import java.io.*;

public class Main{	

	static int N;
	static int M;
	static int[] tree;
	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());

		st = new StringTokenizer(br.readLine());
		
		tree = new int[N + 1];

		for(int i=1; i<N + 1; i++){
			tree[i] = Integer.parseInt(st.nextToken());  	
		}

		BinarySearch();
						
	}

	static boolean check(long h){
		long sum = 0;
		for(int i= 1; i<N+1; i++){
			if(tree[i] > h){
				sum = sum + tree[i] - h;
			}
		}
		
		if(sum >= M){
			return true;
		}else{
			return false;
		}
		
	}

	static void BinarySearch(){
		long L = 0; 
		long R = 1_000_000_000;
		long ans = 0;

		while(L <= R){
			long mid = (L + R) / 2;
			if(check(mid)){
				ans = mid;
				L = mid + 1;
			}else{
				R = mid - 1;
			}
		}

		System.out.println(ans);
	}
}