[BOJ2805] 나무자르기

문제 설명

문제 링크

코드 리뷰

전형적인 이진탐색 문제였다. 이진탐색이지만, 해당되는 조건을 만족시킬 수 있는 답이 여러개일 수 있고, 그 중 가장 알맞는 답을 찾는 문제이므로 나는 이 문제를 파라메트릭 서치로 분류하려한다.

즉, 최적화 문제(적어도 M미터의 나무를 가져가기 위한 높이의 최대값)를 결정문제(이만큼을 잘랐을때 M미터 이상을 집에 가져갈 수 있나?)로 바꿔서 풀면 금방 해결할 수 있다.

탐색의 범위는 자를 수 있는 나무의 길이 범위 0 ~ 가장 높은 나무의 높이로 지정하여 이진탐색을 시작한다.

어떤 나무의 길이가 선택되었을 때, N만큼 돌면서 가져갈 수 있는 나무의 합을 구하고, 그 합이 M보다 크다면 답을 출력할 변수에 저장한다.

이때, 변수에 들어갈 답은 비교를 통해 큰 값을 계속해서 저장시켜나간다.

이렇게 풀면 파라메트릭 서치를 적용하여 문제를 정확하게 푼 것이 된다..(맞겠지)

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


public class BOJ2805_나무자르기 {
	static int N,M;
	static int Max = Integer.MIN_VALUE;
	static int[] arr;
	static int ans;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		arr = new int[N];
		for(int n=0; n<N; n++) {
			arr[n] = Integer.parseInt(st.nextToken());
			if(arr[n]>Max) Max = arr[n];
		}
		bs(0,Max);
		System.out.println(ans);
	}
	static void bs(int left, int right) {
		if(left > right) return;
		int mid = (left+right)/2;
		long sum = 0;
		for(int a:arr) {
			if(a>mid)
				sum+= a-mid;
		}
		if(sum >= M) {
			if(mid >= ans) ans = mid;
			bs(mid+1, right);
		}else {
			bs(left, mid-1);
		}
	}
}