[BOJ] 2805: 나무 자르기 (JAVA)

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

 

풀이

 

이분탐색을 잘 못하는 것 같아서 시도해본 문제.

슬라이딩 윈도우처럼 left++ right--로 풀었더니 바로 시간초과가 발생했다ㅎㅎ

 

나무를 자르기 위해, 높이를 설정해줘야 하는데 초기 mid값은 가장 높은 나무의 절반으로 설정해준다.

그리고 중간값 mid로 자른 나무가 내가 잘라야하는 나무보다 적을 경우

mid값을 낮춰줘야 하는데, 낮출 때는 right 값을 mid -1로 설정해주면

나머지 오른쪽 절반은 볼 필요가 없어진다.

 

 

전체코드

package CodingTest;

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

public class 실버2_2805_나무자르기 {
	static int N, M, left, right;
	static int arr[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		left = 0; right = -1;
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			//현재 가지고 있는 나무의 최대 높이
			right = Math.max(right, arr[i]);
		}
		
		Check();
		
		sb.append(right);
		bw.write(sb.toString());
		bw.close();
	}
	public static void Check() {
		while(left <= right) {
			//내가 가져갈 수 있는 상한선 높이
			int mid = (left+right)/2;
			//내가 총 가져갈 수 있는 나무의 길이
			long tree = 0;
			
			for(int i=0; i<N; i++) {
				if(arr[i] > mid) {
					tree += (arr[i]-mid);
				}else {
					continue;
				}
			}
			
			//아직 부족하면, 높이를 더 낮춰야 함.
			if(tree < M) {
				right = mid -1;
			//이미 충분하면, 높이를 더 높여야 함.
			}else if(tree >= M) {
				left = mid +1 ;
			}
			
			System.out.println(left+" "+right);
		}
	}
}