이분탐색/삼분탐색 #2805: 나무 자르기 [JAVA]

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

2805번: 나무 자르기

 

 

---

 

 

 

문제 접근

 

 

 

 

 

#1654 랜선 자르기 문제와 거의 똑같다..!

 

근데 몇 가지 착각한 부분이 있어서 생각하는 데 시간 걸림 ㅠ

 

 

 

 

 

착각한 부분

 

 

랜선 자르기 문제와 달리 절단기에 설정한 길이를 달리 하면 도출되는 나무의 길이의 합이 겹치지 않으므로 그냥 일반 이분 탐색으로 쓰면 안되나?? 

-> X. 이분탐색은 딱 M이 될 때의 길이를 찾게다는거니까,, 근데 주어진 나무들의 길이에 따라 딱 M이 나올 수도 있고 안나올 수도 있음

 

그래서 일단 길이의 최댓값을 구해야하므로 upper bound를 써야하는 건 ok. 근데 만약 최소 M만큼 가져가야하는데 길이를 어떻게 설정해도 딱 M이 나오는 경우가 없다면 그 M보다 최초로 큰 길이에 대한 높이를 찾아야하는데..
이럴 경우 upper bound 알고리즘이 어떻게 돌아가는지 이해가 안됐는데 간단한 반례로 확인할 수 있다.

 

6 1 
0 2 0 0 0 2

입력이 이렇게 주어지면

절단기 높이) 0 1 2
나무 길이)    4 2 0

절단기 높이에 따른 나무 길이가 위와 같이 되고

직접 upper bound를 해보면 
최적의 높이 바로 위에 값(즉 이값으로 높이를 지정하면 가져가는 나무가 필요보다 부족해짐. 즉, 절단기 높이가 2일 때) 을 high bound로 꺼내주면 거기서 -1을 할 경우 N보다는 많이 가져가더라도 그게 바로 최대높이가 되버린다

 

 

 

 

[ 참고 ] https://st-lab.tistory.com/270

 

 

 

내가 했던 고민이랑 똑같은 거..

 

 

 

 

 

 

 

 

코드

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] arr = new int[n];

		long max = 0;

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if (arr[i] > max) {
				max = arr[i];
			}
		}

		max++;

		long min = 0;
		long mid = 0;

		while (min < max) {

			mid = (min + max) / 2;

			long len = 0;

			for (int i = 0; i < n; i++) {
				if (arr[i] - mid > 0) {
					len += arr[i] - mid;
				}
			}

			if (len < m) { // 길이를 길게 설정해서 len이 작게 나왔으므로 길이를 줄여야한다.
				max = mid;
			} else { // len>=m 길이를 짧게 설정해서 len이 길게 나왔으므로 길이를 늘려야한다. 같을 때는??
				min = mid + 1;
			}
		}

		System.out.println(max - 1);

	}

}