백준 - 2805번 - 나무 자르기

2805번

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

public class Main{

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st  = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] arr = new int[n];
		int max = 0;

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

		int min = 0;
		int mid = 0;

		while (min < max) {
			long len = 0;
			mid = (max + min) / 2;

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

			if (len < m) {
				max = mid;
			}
			else {
				min = mid + 1;
			}
		}
		System.out.println(min-1);
	}
}

풀이

---

저번에 풀었던 랜선 자르기랑 비슷하다.

한줄로 있는 나무를 일정 높이 위로 짤라서 원하는 값을 얻을건데 낭비되는 나무없이 얻으려면 높이를 몇으로 산정해야하나 구하는 문제다.

int 배열에 한줄로 있는 나무들을 담아주고
max값을 찾는다.
mid값을 설정하고 배열에 있는 모든 나무를 mid값으로 빼서 0보다 크면 더해준값 len을 원하는 나무량과 비교해서 부족하면 max= mid 해주고 넘치면 min = mid+1로 선정해서 계속 반복문을 돌려준다.

마지막에 -1을 해서 출력하면 끝!