JAVA
나무의 수 N과 가져가려고 하는 나무의 최소길이 M이 입력된 후 그 다음 줄에는 N개 나무의 각각의 길이가 차례대로 입력된다.
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
절단기의 작동을 이해해보자면 다음 그림과 같다.
이렇게 절단기의 길이를 조정해가며 최소 M 이상의 나무를 가져갈 수 있으며, 절단기의 길이는 최대가 되게끔 조정하면 된다.
1cm씩 조정하면서 최적화된 길이를 찾을 수도 있겠지만 이러한 경우 상당한 시간복잡도를 자랑하게 된다.
따라서 이진탐색을 이용할 것이다.
만약 절단기로 잘랐을 때 가져갈 수 있는 나무의 길이가 최소 나무 길이 M보다 작다면 최소 기준을 충족하지 못하는 것이다. 따라서 절단기의 길이를 줄여야 한다.
Binary Search에서는 절단기 길이의 상한을 줄이는 것이 이에 해당할 것이다.
만약 절단기로 잘랐을 때 가져갈 수 있는 나무의 길이가 최소 나무 길이 M보다 크다면 최소 기준은 충족한다. 하지만 이것이 최선의 결과인지는 모른다. 따라서 일단 결과값에 저장을 해놓고 절단기의 길이를 늘려서 최선의 결과를 계산해볼 수 있도록 한다.
Binary Search에서는 절단기의 길이의 하한을 늘리는 것이 이에 해당할 것이다.
import java.io.*;
public class Main {
public static long result = 0;
public static long tree[];
public static long N,M;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//Input ; 첫 번째 줄
String str = br.readLine();
String[] sp = str.split(" ");
N = Long.parseLong(sp[0]); // 나무의 개수
M = Long.parseLong(sp[1]); // 가져가려고 하는 나무 최소 M미터
//Input ; 두 번째 줄
str = br.readLine();
sp = str.split(" ");
tree = new long[(int)N]; //각각 나무의 길이를 저장하는 배열
long max = 0;
for(int i = 0; i<N;i++) {
tree[i] = Long.parseLong(sp[i]);
max = Math.max(max, tree[i]); // 가장 긴 나무의 길이를 구해서 저장
}
binary(0,max);
bw.write(result+" ");
bw.flush();
}
public static void binary(long start,long end) {
long mid = (start+end)/2; //중간값을 절단기의 높이로 설정한다.
long sum = 0;
if(start > end) return; //만약 탐색하다가 start>end라면 탐색을 멈춘다.
for(int i = 0; i<N;i++) {
//만약 절단기 길이보다 tree의 길이가 길다면
//절단기에 의해 tree가 잘라지므로 result에 추가한다.
if(tree[i]>mid) sum += (tree[i]-mid);
}
//만약 합이 M보다 크다면 최소값을 찾기 위해 절단기의 하한을 높여본다
if(sum >= M) {
result = mid; //일단 저장
if(sum == M) return;
binary(mid+1,end);
}
//만약 합이 M보다 작다면 조건 충족 X
//절단기의 상한을 낮춘다.
else {
binary(start,mid-1);
}
}
}