[백준 2805 JAVA 자바] 나무 자르기

 

문제가 수식으로 되어있으면 참 보기 쉬울탠데

한글로 되어있으니

줄도 길고, 읽기 참 귀찮죠??

 

그림을 그릴게요~

 

다음과 같이 N개 나무들이 있습니다

 

이렇게 동일한 높이로 자릅시다

 

잘린 검은 부분의 합이 M을 넘어야합니다

 

위 조건을 만족하는 높이의 최대값을 구합시다

 

 

코드입니다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		int[] tree = new int[a];
		
		int min = 0;
		int max = 0;
		
		st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<a; i++) {
			tree[i] = Integer.parseInt(st.nextToken());
			if(max < tree[i]) {
				max = tree[i];
			}
		}
		
		while(min < max) {
			int mid = (min + max) / 2;
			long sum = 0;
			
			for(int i=0; i<a; i++) {
				if(tree[i] - mid > 0) { 
					sum += (tree[i] - mid);
				}
			}
			if(sum<b) {
				max = mid;
			}else {
				min = mid + 1;
			}
		}
		System.out.println(min - 1);
	}
}

 

저는 이 문제 푸는데 좀 힘들었습니다 ㅠㅠ

 

 

조건을 잘 생각하고

 

어? 이런 경우에는 어떻게 출력을 해야하지? 고민하고

 

시간초과!!!!!

 

모든 문제에는 '알고리즘 분류' 항목에

약간의 힌트가 들어가는데

저는 그걸 안보고 풀거든요,,,그래서 좀 힘들었습니다

while(min < max) 부분이 이분탐색을 이용하는 부분입니다