[ 백준 2805 ] 나무자르기 - Java

문제 링크

http://boj.kr/2805

2805번: 나무 자르기

문제 풀이

이 문제는 이분탐색에 분류되어 있는 문제이다.

 

이분탐색은 정렬되어있는 배열에서 원하는 값을 찾아가는 탐색법이다.

 

그런데 이 문제는  parametric search이라는 스킬을 이용해서 푼다.

 

간단하게 설명하자면 이분탐색은 시작과 끝의 중간점을 찾고 찾는 값이 더 크면 시작점을 중간점으로 잡고, 더 작으면 끝점을 중간점으로 잡고 다시 탐색하는것을 찾을 때 까지 반복한다.

 

그래서 원하는 값을 찾으면 종료시키는데, parametric search는 원하는값을 찾아도 계속해서 찾아나간다고 볼 수 있다.

 

자세한 코드는 다음과 같다.

소스 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();
		int [] treeLen = new int [N];
		int max = 0;
		int min = 1;
		int answer = 0;
		for (int i = 0; i < treeLen.length; i++) {
			treeLen[i] = sc.nextInt();
			max= Math.max(max, treeLen[i]);
		}
		long pivot = 0;
		while(max>=min) {
			long sum = 0;
            pivot = (0L+max +min) /2;
			for (int i = 0; i < treeLen.length; i++) {
				long len = treeLen[i] -pivot;
				if(len>0) sum += len;
			}
			if(sum >= M) {
				min = (int) (pivot +1);
				answer = Math.max(answer, (int)pivot);
			}else {
				max = (int) (pivot -1);
			}
		}
		System.out.println(answer);
	}

}