/ BOJ

BOJ_2805_나무자르기_JAVA

문제 : 나무자르기

링크 : BOJ_2805_나무자르기

접근 방식

이분탐색을 이용하여 문제를 풀 수 있다.

먼저 0부터 최대 나무의 길이의 절반만큼 길이를 계산해보고, 가져가야하는 나무의 길이보다 짧으면 자르는 최대 길이를 그 절반에서 -1 한 만큼으로 수정해주고, 만약 가져가야하느 나무의 길이보다 길면 자르는 시작 위치 기준을 중간 위치에서 +1 해준다. 이러한 방식으로 나무를 절반씩 탐색해가면서 원하는 길이 이상으로 얻을 수 있는 가장 높은 위치를 구할 수 있다.

소스 코드

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

public class BOJ_2805_나무자르기 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine()," ");

		int N = Integer.parseInt(st.nextToken());

		long M = Long.parseLong(st.nextToken());

		long arr[] = new long[N];

		st = new StringTokenizer(in.readLine()," ");

		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}


		long max = 0;
		for(int i=0;i<N;i++) {
			max = Math.max(max, arr[i]);
		}
		long start = 0;

		while(start <= max) {
			long half = (start + max)/2;
			long sum = 0;
			for(int i=0;i<N;i++) {
				long temp = arr[i] - half;
				sum += (temp>0) ? temp: 0;
			}
//			System.out.println(sum);
			if(sum >= M) {
				start = half+1;
			}else{
				max = half-1;
			}
		}
		System.out.println(max);

	}

}