99클럽 코테 스터디 6일차 TIL (2805번: 나무 자르기)

문제

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

---

학습 키워드

• 이분 탐색

 

시도

• 입력 제한 사항을 제대로 읽지 않고 풀어서 시간 초과 발생. 주어진 나무들의 높이 중 가장 큰 높이부터 1씩 줄여가면서 M을 만족하는 가장 높은 나무의 높이를 계산했다. 나무 높이의 최대값은 1,000,000,000이므로, 1초를 훨씬 넘는다. 처음에는 시간초과를 했을 때, 입력 값이 많아서 그런줄 알고 BufferedReader와 StringTokenizer를 사용해서 입력을 받았다. 
  • 나무의 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.
• (성공) 이분 탐색을 통해 범위를 줄여가면서 최적의 해를 구하는 방식으로 풀었다.

 

풀이

• 0부터 나무 높이의 최대값(1,000,000,000)까지 이분 탐색을 진행했다. 

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

public class Main {

	private static int N;
	private static long M;
	private static long[] arr;
	private static long answer = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 나무의 수
		M = Integer.parseInt(st.nextToken()); // 필요한 나무의 미터

		arr = new long[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		binarySearch(0, 1000000000);
		System.out.println(answer);
	}

	private static void binarySearch(long left, long right) {
		if (left > right) {
			return ;
		}
		long middle = (left + right) / 2;
		long sum = 0;
		for (int i = 0; i < N; i++) {
			if (middle >= arr[i]) {
				continue;
			}
			sum += arr[i] -  middle;
		}
		if (sum >= M) {
			answer = Math.max(answer, middle);
			binarySearch(middle + 1, right);
		} else {
			binarySearch(left, middle - 1);
		}
	}
}