[백준] 2805 : 나무 자르기 (JAVA)

2805번: 나무 자르기

Solution

문제를 처음 확인했을 때 이분탐색으로 풀어야겠다 하는 생각이 들어서 금방 풀겠다 싶었는데 신경 써줄 것들이 조금 있었다.

1. 입력 값의 범위가 크다는 것
2. 조건을 충족하는 mid 중에 최대가 되는 mid 를 골라야 한다는 것

정수형 타입	할당되는 메모리의 크기	데이터의 표현 범위
byte	1바이트	-128 ~ 127
short	2바이트	-2^15 ~ (2^15 - 1)
		-32,768 ~ 32,767
int	4바이트	-2^31 ~ (2^31 - 1)
		-2,147,483,648 ~ 2,147,483,647
long	8바이트	-2^63 ~ (2^63 - 1)
		-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

나무의 높이가 1,000,000,000보다 작거나 같은 양의 정수 또는 0이므로 산술 시 int 형 범위를 초과할 수 있다. (long으로 선언)

기본적인 이분탐색 코드는 아래와 같다.

public int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (target == arr[mid]) {
            return mid;
        }else if (arr[mid] < target) {
            start = mid + 1;
        }else if (target < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("can't find target.");
}

위 문제에서 답이 될 mid 는 lt (stard) ~ rt (end) 사이에 존재한다
lt = (가장 높은 나무 하나만 베어서 M을 충족해야 하는 경우)
rt = (길이가 모두 같은 M개의 나무를 1만큼 벨 경우)

 

Code

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

class Main
{
	public static long count(long[] arr, long M, long L) {
		long num=0;
		for(long x:arr) {
			if(M<num) return num;
			if(x>L) {
				num+=(x-L);
			}
		}
		return num;
	}
	
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine()," ");
		long N=Long.parseLong(st.nextToken());
		long M=Long.parseLong(st.nextToken());
		
		long[] arr = new long[(int) N];
		long max=0;
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<N;i++) {
			arr[i]=Long.parseLong(st.nextToken());
			max=Math.max(max, arr[i]);
		}

		long lt=max-M;
		long rt=max-1;
		long ans=0;
		while(lt<=rt) {
			long mid=(lt+rt)/2;
			long tmp=count(arr,M,mid);
			if(tmp==M) {
				ans=mid;
				break;
			}
			if(tmp>M) {
				if(ans<mid)
					ans=mid;
				lt=mid+1;
			}
			else rt=mid-1;
		}

		System.out.println(ans);
	}
}