[백준/Java] 2085 나무 자르기

조건

1. 처음에는 나무의 수 N과 필요로 하는 나무의 길이 M이 주어진다.

2. (나무의 최대의 수 * 필요로 하는 나무의 길이)를 한다면 int의 범위를 넘어가기 때문에 Long으로 계산을 해준다.

3. 하지만 정답은 높이의 최대값은 int이기 때문에 정답의 변수는 int로 해야한다.

예제 입력

해설

이분 탐색으로 해당 문제를 해결할 건데 이분 탐색을 통해 높이를 구하고 for문으로 해당 높이에서
나무의 길이가 구해지는 탐색을 한다.

코드

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



public class Main {
	
	static int N, M;
	static int[] A,B;
	
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();

	static void input() {
		
		N = scan.nextInt(); // 나무의 수를 받음
		M = scan.nextInt(); // 필요로 하는 나무의 높이를 받음
		A = new int[N + 1];
		
		for(int i=1;i<=N;i++) {
			A[i] = scan.nextInt();
		}
		

		
	}

	
	static boolean findAns(int B) {
		long sum = 0;
		for(int i = 1;i<=N;i++) {
			if(A[i]>B) { // 필요로 하는 나무의 높이와 비교 나무 가 크면 빼기를 통해 
				sum += A[i] - B; // 더해준다.
			}
		}
		return sum >= M;

	}
	

	
	
	
	static void find() {
		long L =0, R = 2000000000, ans=0; // 나무의 최소 길이 최대 길이를 설정해줌
		
		while(L<=R) {
			int mid = (int)((R + L)/ 2); // Long을 int로 변환해서 mid로 넣어줌
			if(findAns(mid)) { //findAns 함수 실행 true이면 ans에 해당 mid가 들어감
				ans = mid;
				L = mid + 1;
			}else {
				R = mid - 1;
			}
			
		}
        	System.out.println(ans);
		}

		
		
	

	public static void main(String[] args) {
		input();
		find();
	}
	
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		Long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			}catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}