백준 2805 - 나무 자르기 ( JAVA )

출처 - 백준 프로그램

2805번: 나무 자르기

---

알고리즘

이분탐색을 활용해야 하는 문제이다. 

나무의 갯수와 길이가 큰 수이기 때문에 모든 경우의 수를 탐색하게 되면 시간초과가 발생할 수 있다. 

- 탐색 범위 : 0 ~ '입력받은 나무들 중 가장 긴 길이'   ( 더 길어지면 땅 파는거다,, )

 

 

1. min = 0 , max = '가장 긴 나무' 로 초기화하여 탐색을 시작한다. 

 

2. min 과 max 값 사이의 중간값 mid 를 찾는다. 

 

3. 주어진 나무들 중, mid 값일 때 잘려나가는 나무조각의 합 sum을 구한다. 

 ( * mid 보다 나무의 길이가 더 길어야지만 잘릴수 있음 !! ) 

 

4-1. sum >= 필요한 나무조각 M 이라면, 나무조각이 덜 필요한 것이므로 절단기의 높이를 높인다. 

   즉, mid 값을 기준으로 우측을 탐색하면 된다.  mid+1 ~ max 

 

4-2. sum < M 일 경우, 나무조각이 더 필요한 것이므로 절단기의 높이를 낮춘다. 

   즉,  mid 값을 기준으로 좌측을 탐색하면 된다.  min ~ mid-1 

 

5. 위의 과정을 max < min 일 때까지 반복하며 탐색한다. ( max < min 일 경우 탐색을 더 이상 못함 ) 

 

6. sum == M 일 때, mid 값에 +1 했으므로, mid -1 인 max 값을 최종 출력한다. 

 

 

 + 신경써야 할 부분 

: 나무의 길이가 억단위로 주어지기 떄문에, mid 값을 구하기 위해 더하면 overflow 가 발생할 수 있다.

때문에, min, max을 long형 타입으로 해줘야 한다 !!. 

---

소스 코드

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

public class Solution_BaekJoon_2805 {
	public static void main(String[] args) throws Exception {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st= new StringTokenizer(br.readLine(), " ");
		int N= Integer.parseInt(st.nextToken()); // 나무의 갯수 
		int M= Integer.parseInt(st.nextToken()); // 필요한 나무 길이 
		
		int tree[] = new int[N]; 
		
		long min=0; 
		long max=0; 
		
		st= new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<tree.length; i++) {
			tree[i] = Integer.parseInt(st.nextToken()); //나무의 높이 
			if (tree[i] > max ) max= tree[i]; 
		}
		
		
		while(max>=min) {	
			long mid = (max+min)/2;		
			long sum =0; 
			
			for(int t : tree) {
				if(t>mid) sum+= t-mid; 
			}
			//  너무 많이 잘랐음, 높이 높여도 됨 
			if(sum >= M ) {
				min = mid+1; 
			}
			else {
				max= mid-1; 
			}
		} //end of while 
		
		System.out.println(max);
	}
}

 끗