[백준/JAVA] 2805 - 나무 자르기

문제 정보

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

 

문제

 

문제 해결 과정

완전 탐색 풀이

절단기 높이를 최대 높이인 1,000,000,000부터 시작해서 0이될때까지 1씩 줄여보면서, 현재 절단기로 자른 나무 높이의 합이 필요 나무 길이 이상인지 확인하면 된다. 이 경우에 시간복잡도는 O(NH)이고 (N: 나무의 수, H: 절단기의 최대 높이), 문제 조건에서 N의 최대 10^6이고 H는 최대 10^9이므로, O(NH) = O(10^15)이므로 시간 제한인 1초를 초과하게 된다.

따라서, 절단기 높이를 1씩 줄어가면서 자른 나무 높이의 합이 필요 나무 길이 이상인지 확인하는 방식은 적합하지 않다.

 

이분 탐색 풀이

이분 탐색을 위해서는 "데이터가 정렬이 되어있어야 한다"는 조건을 만족해야 한다. 절단기의 높이가 최대인 1,000,000,000일때 자른 나무의 높이 합이 제일 최소이고, 높이가 최소인 0일때 자른 나무의 높이 합이 제일 최대이다. 더 생각해보면, 절단기의 높이가 높을수록 자른 나무의 높이 합은 작아진다. 즉, 절단기의 높이와 자른 나무의 높이 합은 반비례한다.

절단기 높이에 따른 나무 높이의 합 데이터도 정렬되어 있으므로, 이분 탐색을 사용할 수 있다. 그렇다면 절단기 높이 H를 1씩 줄여가는 것이 아닌, 이분 탐색을 이용하여 절단기 높이를 변경하면서 현재 절단기 높이로 자른 나무 높이의 합이 필요 나무 길이 이상인지 확인해보자.

1) 자른 나무 높이의 합 > 필요 나무 길이 : 더 높은 절단기로도 필요 나무 길이를 얻을 가능성 있음
2) 자른 나무 높이의 합 < 필요 나무 길이 : 더 낮은 절단기로 잘라야 함
3) 자른 나무 높이의 합 == 필요 나무 길이 : 해당 절단기가 필요 나무 길이를 얻는 최대 높이인 절단기임

 

이분 탐색 풀이의 시간복잡도

절단기의 높이를 이분 탐색을 할 때 소요되는 시간복잡도는 O(logH)이다. (H: 절단기의 최대 높이) 또한, 해당 절단기로 모든 나무를 자르고 합을 구하는 시간복잡도는 O(N) (N: 나무의 수)이다. 따라서, 총 시간복잡도는 O(NlogH)이고, 문제 조건에서 N은 최대 10^6이고 H는 최대 10^9이므로, O(NlogH) = O(10^6 * log10^9) ≒ O(10^6 * log (2^10)^3) ≒ O(10^6 * log 2^30) ≒ O(10^6 * 30) ≒ O(3 * 10^7)이므로, 문제 제한인 1초에 충분하다.

 

참고

전에 포스팅했던 Lower bound와 Upper bound와 관련된 문제였다.

2024.06.18 - [Data Structure & Algorithm/알고리즘(Algorithm)] - 04. 이진탐색

 

코드

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 나무의 수
		int m = Integer.parseInt(st.nextToken()); // 집에 가져갈 나무의 길이
		
		int[] tree = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			tree[i] = Integer.parseInt(st.nextToken());
		}
		
		int left = 0;
		int right = 1_000_000_000;
		int height = 0; // 최대 절단기 높이
		
		while(left <= right) {
			int mid = (left + right)/2; // 현재 절단기 높이
			
			long sum = 0; // 현재 절단기 높이일 때, 잘린 높이들의 합
			// 절단기로 나무들을 자름
			for(int i=0; i<n; i++) {
				int cut = (tree[i] - mid) > 0 ? tree[i] - mid : 0; // '나무 높이 > 절단기'이면 잘림
				sum += cut;	
				
				if(sum > m) break;
			}
			
			if(sum > m) { // 더 높은 절단기로도 필요 나무 길이 얻을 가능성 있음
				left = mid+1;
				height = Math.max(mid, height);
			}
			else if(sum < m){ // 더 낮은 절단기로 잘라야 함
				right = mid-1;
			}
			else { // 해당 절단기가 필요 나무 길이를 얻는 최대 높이의 절단기임
				height = Math.max(mid, height);
				break;
			}
			
		}
		
		System.out.println(height);
		
	}
}