[백준 2805] 나무 자르기 (S2)

 

📍 문제 

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

 

📍 문제 풀이

이분탐색을 이용하는 문제다. 

이분탐색에서 가장 중요한 점은 내가 구해야하는 값이 무엇인지를 정확히 알고있는 것이다.

이 경우는 절단기에 설정할 수 있는 높이의 최대값이다.

 

그렇다면 이 값들을 아래와 같이 초기화해줄 수 있다.

절단기에 설정할 수 있는 높이 start의 최소값은 0

절단기에 설정할 수 있는 높이의 최대값 end는 나무들의 높이 중 최대값

 

배열의 원소들을 순회하면서 해당 나무들에서 높이 mid를 빼주어 합을 구해야한다.

 

이때 설정한 높이 mid가 실제 나무의 높이보다 클 수 있기 때문에 이 경우에는 가져갈 수 있는 나무가 0이다. 반대의 경우에는 배열의 값 - mid 값이기 때문에 두 값 중 더 큰 값을 구해서 더해줘야한다.

그리고 나무 한 그루의 최대 길이가 1,000,000,000 (10억)이기 때문에 합산을 나타내는 sum변수의 자료형은 int 타입이 아닌 long 타입으로 지정해줘야한다. 

 

이렇게 구한 sum과 m값을 비교해 sum < m 이라면 상근이가 가져갈 나무가 너무 작은 경우이기 때문에 절단기의 설정 높이를 낮춰야한다. 반대의 경우는 높여야한다. 

 

📍 전체 코드

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

public class boj_2805 {
	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[] trees = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			trees[i] = Integer.parseInt(st.nextToken());
		}

		int start = 0;
		int end = Arrays.stream(trees).max().getAsInt(); // 나무 높이의 최대값

		while (start < end) {
			int mid = (start + end) / 2;

			long sum = 0;	// 상근이가 가져갈 수 있는 나무의 합
			for (int tree : trees) {
				// 절단기 설정 높이가 나무의 높이보다 큰 경우 : 0
				// 작거나 같은 경우 : tree - mid
				sum += Math.max(tree - mid, 0);
			}

			if (sum < m) {    // 너무 조금 자른 경우 -> 높이는 내려야함
				end = mid;
			} else {	// 너무 많이 자른 경우 -> 높이를 올려야함
				start = mid + 1;
			}
		}
		System.out.println(start  - 1);

	}
}