[BAEKJOON_2805 - JAVA] 나무자르기

문제

www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

풀이

• 처음에는 부르트포스로 접근 → N(1,000,000) * H(1,000,000,000) → 100만 * 10억 → 시간초과 발생
• binary search 사용 → O(N * logM)
• 잘라낸 나무들의 길이의 합이 자료형의 범위를 벗어날 수 있으므로, long형 타입 사용

 

 

과정

1. 입력받은 나무들의 정보를 오름차순으로 정렬
2. 이분탐색
3.  minHeight와 maxHeight에 중간값이 들어갈 때 각각 +1, -1을 하지 않는다면 시간초과 발생

 

 

알고리즘 지식

• 이분 탐색

 

 

JAVA코드

package BaekJoon_2020_12_22__23;

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

/**
 * @packageName : BaekJoon
 * @fileName : BJ_2805_나무자르기.java
 * @author : Mingeon
 * @date : 2020. 12. 22.
 * @language : JAVA
 * @classification : 이분탐색
 * @time_limit : 1sec
 * @required_time : 20:10 ~ 20:51
 * @submissions : 3
 * @description 
 * 1. 이진 탐색을 언제 사용하는가
 */

public class BJ_2805_나무자르기 {

	static int N; // 나무의 수
	static int M; // 원하는 나무의 길이
	static int[] trees; // 나무들의 높이 정보

	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()); // 원하는 나무의 길이
		trees = new int[N]; // 나무들의 정보

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			trees[i] = Integer.parseInt(st.nextToken());
		} // End of input
		Arrays.sort(trees); // 오름차순으로 정렬
		int len = trees.length; // 나무 배열의 길이

		// 이분탐색을 위한 변수
		int maxHeight = trees[len - 1]; // 최대 길이
		int minHeight = 0; // 최소 길이
		int middle = 0; // 중간값

		// 이분 탐색
		while (maxHeight >= minHeight) {
			middle = (minHeight + maxHeight) / 2; // 중간값

			int cutTree = 0; // 잘라낸 나무 길이
			long cutSumTree = 0; // 잘라낸 나무 길이들의 합 (나무길이들의 합이므로 int형을 넘어갈수 있다.)

			// 잘라낸 나무 길이들의 합 구하는 과정
			for (int i = 0; i < len; i++) {
				cutTree = trees[i] - middle; // 중간값으로 나무를 자른다.(중간값으로 자른 뒤 범위를 좁혀 간다)

				// 잘린 나무가 없는 경우 0
				if (cutTree < 0) {
					cutTree = 0;
				}

				// 잘라낸 나무길이 합
				cutSumTree += cutTree;
			}

			// 잘라낸 나무들의 합이 최소한으로 가져야 하는 나무 길이보다 큰 경우
			if (cutSumTree >= M) {
				minHeight = middle + 1;
			}
			// 잘라낸 나무들의 합이 최소한으로 가져야 하는 나무 길이보다 작은 경우
			else if (cutSumTree < M) {
				maxHeight = middle - 1;
			}
		} // End of while

		System.out.println(maxHeight);
		br.close();
	}

}