#2805 : 나무 자르기

풀이방법

사용된 것:

이분 탐색

 

2022.06.15

랜선 자르기 문제와 동일한 방식으로 풀면 된다.

#1654 : 랜선 자르기

특정 높이로 기계를 설정하고 나무를 잘랐을 때 얻을 수 있는 목재의 길이가 M 미만인지 아닌지를 판별하여 이분 탐색을 한다.

 

코드

Java(2022.06.15)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) trees[i] = Integer.parseInt(st.nextToken());
		
		Arrays.sort(trees);
		
		int start = 1;
		int end = trees[n-1]+1;
		
		//이분탐색 하기
		while(start<end) {
			int mid = (start+end)/2;
			long sum = 0;
			for(int i: trees) if(i>mid) sum += i-mid;
			
			if(sum<m) end = mid;
			else start = mid+1;
		}
		
		//정답 출력
		System.out.print(end-1);
	}

}