[백준/Java] 2805 나무 자르기

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

문제 요약

N개의 나무가 있을 때, 특정 높이 H로 잘라서 얻은 목재의 총 길이가 M 이상이 되는 최대의 H 구하기
N은 최대 백만, M은 최대 20억, H는 최대 10억

---

문제 접근

이분탐색...!
이분탐색을 통해 목재의 총 길이가 M이 되는 최대 높이를 구하면 된다.
"이분 탐색(Binary Search) 헷갈리지 않게 구현하기" 정리 참고

---

풀이

기본적인 아이디어는 다음과 같다.

1. (정리 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main {
    static int N, M;
    static int[] trees;
    
    // 입력 받는 함수
    public static void getInput() 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];
    	
    	StringTokenizer st2 = new StringTokenizer(br.readLine());
    	for (int i = 0; i < N; i++) {
    		trees[i] = Integer.parseInt(st2.nextToken());
    	}
    }
    
    // 목재의 총 길이가 M 이상인지 확인하는 함수
    public static boolean isSatisfied(int cutHeight) {
    	long total = 0;
    	
    	for (int i = 0; i < N; i++) {
    		int cutted = Math.max(0, trees[i]-cutHeight);
    		total += cutted;
    	}
    	
    	if (total >= M) {
    		return true;
    	}
    	return false;
    }
    
    // 이분탐색을 통해 조건을 충족하는 최대 높이를 찾는 함수
    public static int findMaxHeight(int low, int high) {
    	
    	while (low + 1 < high) {
    		int mid = (low + high) / 2;
    		
    		// 해당 높이로 목재가 충분하다면 그 이상의 영역을 찾아야 함
    		if (isSatisfied(mid)) {
    			low = mid;
    		}
    		// 해당 높이로 목재가 부족하다면 그 미만의 영역을 찾아야 함
    		else {
    			high = mid;
    		}
    	}
    	return low;
    }
    
    public static void main(String[] args) throws IOException {
        getInput();
        
        int maxHeight = findMaxHeight(-1, 1_000_000_001);
        
        System.out.println(maxHeight);
    }
}

---

회고

(추가 예정)