백준[2805] 나무 자르기

박지호·2022년 7월 11일
0

백준 2805 나무자르기

Language

JAVA

Input

나무의 수 N과 가져가려고 하는 나무의 최소길이 M이 입력된 후 그 다음 줄에는 N개 나무의 각각의 길이가 차례대로 입력된다.

Output

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

문제 이해

절단기의 작동을 이해해보자면 다음 그림과 같다.

이렇게 절단기의 길이를 조정해가며 최소 M 이상의 나무를 가져갈 수 있으며, 절단기의 길이는 최대가 되게끔 조정하면 된다.
1cm씩 조정하면서 최적화된 길이를 찾을 수도 있겠지만 이러한 경우 상당한 시간복잡도를 자랑하게 된다.

따라서 이진탐색을 이용할 것이다.

  1. 만약 절단기로 잘랐을 때 가져갈 수 있는 나무의 길이가 최소 나무 길이 M보다 작다면 최소 기준을 충족하지 못하는 것이다. 따라서 절단기의 길이를 줄여야 한다.

    Binary Search에서는 절단기 길이의 상한을 줄이는 것이 이에 해당할 것이다.

  2. 만약 절단기로 잘랐을 때 가져갈 수 있는 나무의 길이가 최소 나무 길이 M보다 크다면 최소 기준은 충족한다. 하지만 이것이 최선의 결과인지는 모른다. 따라서 일단 결과값에 저장을 해놓고 절단기의 길이를 늘려서 최선의 결과를 계산해볼 수 있도록 한다.

    Binary Search에서는 절단기의 길이의 하한을 늘리는 것이 이에 해당할 것이다.

Code

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);
		}
	}

}

check

  • binary search의 대표적인 문제
  • 상한과 하한을 조정하는 조건을 생각해주면서 짠다.
  • 재귀를 사용할 때, 재귀 종료 조건은 항상 명시를 해주어야 한다!

0개의 댓글