백준 2805번 <나무 자르기>

백준 알고리즘 2805번

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

2805번: 나무 자르기

---

2805번

M미터의 나무가 필요하다. N개의 나무의 높이를 알고 있을 때, 절단기의 높이를 최대 몇으로 지정해야 M미터의 나무를 얻을 수 있는지 구하여라. 

절단기에 나무를 넣고 자를 때, 잘리고 남은 나무를 얻을 수 있다. 즉 10 15 17 이 있고 절단기의 높이가 13이라면 0 + 2 + 4=6 m의 나무를 얻을 수 있다.

 

입력으로 첫 줄에 나무의 개수 N과 M이 주어지고 그 다음 줄에 각 나무들의 높이가 주어진다.

 

출력으로 최대 몇 m로 지정할 수 있는지 구해서 출력하면 된다. 

---

문제 해결

이분탐색을 이용해 구할 수 있다. 

이분탐색을 이용해 mid 값을 절단기에 설정할 수 있는 높이로 활용한다.

만약 mid값으로 설정하여 얻는 나무의 양이 M보다 작다면 더 많은 나무를 얻어야 하기 때문에 mid 값을 줄여야 한다.

즉, end 값을 mid-1로 한다.

만약 mid값으로 설정하여 얻는 나무의 양이 M보다 크거나 같다면 나무를 덜 잘라도 되기 때문에 mid 값을 키워야 한다.

즉, start 값을 mid+1로 한다.

나무의 높이가 다양하기 때문에 M과 같은 양의 나무를 얻을 수 있는 절단기 설정 높이가 여러 개 일 수 있어서 같은 경우에도 mid 값을 키워주도록 한다. 

(mid 값을 키워주면 같은 양의 나무를 얻다가 어느 순간부터는 적은 양의 나무가 얻어진다.)

---

코드

package boj2805;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
 * binary search로 높이를 구했다.
 * mid값이 절단기에 설정할 수 있는 높이 값.
 * 만약 mid값으로 잘랐을 때 얻는 나무의 양이 M보다 적다면 mid 값을 작게 해서 더 잘리도록 해줘야 한다.
 * -> end를 mid-1로
 * 만약 mid값으로 잘랐을 때 얻는 나무의 양이 M과 같거나 크다면 mid 값을 크게 해서 덜 잘리도록 해줘야 한다.
 * -> start를 mid+1로
 * -> 최대한 덜 자르도록 해야 하기 때문에 M과 같을 때에도 해준다.
 * */

public class Main {
	static int N, M;
	static long[] trees;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inArr = br.readLine().split(" ");
		N = Integer.parseInt(inArr[0]);
		M = Integer.parseInt(inArr[1]);

		trees = new long[N];
		inArr = br.readLine().split(" ");
		for (int i = 0; i < N; i++) {
			trees[i] = Long.parseLong(inArr[i]);
		} // end input

		long start = 0;
		long end = 1000000000;
		long ans = 0;
		while (start <= end) {
			long mid = (start + end) / 2;
			long acc = sum(mid);

			if (acc < M) {
				end = mid - 1;
			} else {
				start = mid + 1;
				ans = Math.max(ans, mid);
			}
		}
		System.out.println(ans);

	}

	public static long sum(long mid) {
		long acc = 0;
		for (int i = 0; i < N; i++) {
			if (trees[i] > mid) {
				acc += trees[i] - mid;
			}
		}
		return acc;
	}

}

---

결과

---