백준 2805번 - 나무 자르기

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

2805번: 나무 자르기

 

 

 

 

 

이분탐색 알고리즘을 사용하는 문제이다. 이전에 프로그래머스에서 '입국심사' 문제를 풀었던 것이 도움이 되었다.

 

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

 

 

 

절단기의 높이(H)를 이분탐색을 통해 구한다.

 

1. 이분탐색을 위해 절단기의 높이를 설정하는 데 쓰일 나무 배열을 정렬한다.

2. 가능한 절단기의 높이(H)의 최솟값(하한값)과 최댓값(상한값)을 구한다. 

3. mid 값으로 절단하고 들고갈 나무들의 높이 합을 구한다.

4. 합을 적어도 필요한 나무 높이(M)과 비교한다

 - 합이 M보다 더 작으면->상한값을 줄인다.

 - 합이 M보다 크거나 같으면 ->하한값을 줄이고 절단기에 설정할 수 있는 높이(정답)를 mid으로 저장한다.

5. 하한값<= 상한값일 때까지 반복하여 절단기에 설정할 수 있는 높이(정답)을 갱신해나간다.

 

 

 

 

 

코드

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

public class CuttingTree {

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

		String[] input1 = br.readLine().split(" ");
		int N = Integer.parseInt(input1[0]);
		int M = Integer.parseInt(input1[1]);
		
		int[] tree = new int[N];
		
		String[] input2 = br.readLine().split(" ");
		for(int i = 0; i < N; i++) {
			tree[i] = Integer.parseInt(input2[i]);
		}
		
		Arrays.sort(tree); //이분 탐색을 위한 정렬
		
		int answer = 0;
		int low = 0; //H 최소
		int high = tree[tree.length - 1]; //H 최대(가장 큰 나무)
		
		while(low <= high) {
			int mid = (low + high) / 2;
			
			long sum = 0;
			for(int i = 0; i < N; i++) {
				if(tree[i] > mid) { //절단하고 남으면
					sum += (tree[i] - mid); //들고 가기
				}
			}
			
			if(sum < M) { //M보다 더 적은 나무 가져가면
        		high = mid - 1; //H 줄이기
        	} else { //M보다 더 많은 나무 가져가면
        		low = mid + 1; //H 늘리기
        		answer = mid;
        	}
		}
		
		System.out.println(answer);
	}

}

 

*주의할 점*

높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이므로 자르고 남은 길이의 합은 int가 담을 수 있는 크기(2,147,483,647)보다 클 수가 있다. 따라서 자료형을 long으로 해야 한다. 처음에 아무 생각 없이 int로 했다가 틀렸다.

 

 

 

 

 

결과