[백준] 2805 나무 자르기 - 파라매트릭 서치(Paramatric Search) JAVA

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

코드설명

파라매트릭 서치 문제입니다.

 

 

각 탐색때마다, 잘라서 가져갈 수 있는 나무길이를 상근이가 가져갈 나무길이 M과 비교하여 

상근이가 가져갈 나무길이보다 잘라놓은 나무길이가 더 작거나 같다면, start = middle + 1 처리를 통해 더 많이 자릅니다.

반면에, 상근이가 가져갈 나무길이 M보다 더 많다면, end = middle - 1 작업을 통해서 덜 자릅니다.

위의 과정을 반복하다보면, M과 같거나 가장 근접한 값으로 탐색하게 되고, 

탐색을 진행하다보면, end가 줄어들면서 반복문이 끝이 나고, end를 출력하면 됩니다

if(treeLength >= M) {
    start = middle + 1;
}else {
    end = middle - 1;
}

 

또한 유의해야할점은,

단순히 문제조건에

- 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

- 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

 

여기서 단순히 각 자료형의 범위를 보면 아슬아슬하게 int 를 통과하는 조건을 확인했지만,. 

나무를 잘라서 차이를 구할때는 합계산이 들어가기에 long을 써야 문제의 조건을 통과합니다.

 

절단기의 높이가 올라가면, 오히려 상근이가 가져가야할 나무의 길이가 줄어든다는점을 유의해야합니다.

코드

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

public class Main {
	public static int N, M, K = 0;
	public static int[] arr; 
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	int end = 0;
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    		end = Math.max(end, arr[i]);
    	}
    	
    	paramatricSearch(0, end);
    }
    
    public static void paramatricSearch(long start, long end) {
    	long left = start;
    	long right = end;
    	
    	while(left <= right) {
    		long middle = (left + right) / 2; //절단기에 설정할 높이.
    		
    		long sum = 0;
    		for(int i=0;i<N;i++) {
    			sum += (arr[i] - middle) > 0 ? arr[i] - middle : 0;
    		}
    		
    		//만약 상근이가 가져가려고하는 나무의 길이 M미터보다 더 많이있다면, 절단기의 높이를 올려줘야합니다. 
    		if(sum >= M) {
    			left = middle + 1;
    		} else if(sum < M) {
    			right = middle - 1;
    		}
    	}
    	
    	System.out.println(right);
    }
    
    
}

 

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


public class Main {
	
	public static int N, M;
	public static long[] arr;
	public static long value = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	arr = new long[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    		value = Math.max(value ,  arr[i]);
    	}
    	
    	paraMatricSearch();

    }
    
    public static void paraMatricSearch() {
    	long start = 0;
    	long end = value;
    	
    	while(start <= end) {
    		long middle = (start + end) / 2;
    		
    		long treeLength = 0;
    		for(int i=0;i<N;i++) {
    			long diff = arr[i] - middle;
    			if(diff > 0) {
    				treeLength += diff;	
    			}	
    		}
    		
//    		System.out.println(middle+" "+treeLength);
    		if(treeLength >= M) {
    			start = middle + 1;
    		}else {
    			end = middle - 1;
    		}	
    	}
    	System.out.println(end);
    	
    }
    
}

 

정답코드 3입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, H, W, K, M;
	public static int answer = 0;
	public static int[] arr;
	public static void main(String[] args) throws IOException{
		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 i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(optimize(0, 1000000001));
		
	}
	
	public static boolean decision(int cutterHeight){
		long ret = 0;
		for(int i=0;i<N; i++) {
			ret += (arr[i] - cutterHeight) > 0 ? arr[i] - cutterHeight : 0;
		}
		return ret >= M;
	}
	
	public static int optimize(int lo, int hi) {
		int left = lo;
		int right = hi;
		
		while(left + 1 < right) {
			int mid = (left + right) / 2;
			//만약 나무를 잘랐을떄, 원하는 값만큼 자를 수 있다면, 절단기의 높이를 증가시킵니다.
			if(decision(mid) == true) {
				left = mid;
			}
			else if(decision(mid) == false){
				right = mid;
			}
		}
		return right - 1;
		
	}
}

 

for문으로 처리해도 가능합니다. 100번의 이진탐색으로 원하는 값을 찾을 수 있습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, H, W, K, M;
	public static int answer = 0;
	public static int[] arr;
	public static void main(String[] args) throws IOException{
		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 i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(optimize(0, 1000000001));
		
	}
	
	public static boolean decision(int cutterHeight){
		long ret = 0;
		for(int i=0;i<N; i++) {
			ret += (arr[i] - cutterHeight) > 0 ? arr[i] - cutterHeight : 0;
		}
		return ret >= M;
	}
	
	public static int optimize(int lo, int hi) {
		int left = lo;
		int right = hi;
		
		for(int it = 0; it<100; it++) {
			int mid = (left + right) / 2;
			//만약 나무를 잘랐을떄, 원하는 값만큼 자를 수 있다면, 절단기의 높이를 증가시킵니다.
			if(decision(mid) == true) {
				left = mid;
			}
			else if(decision(mid) == false){
				right = mid;
			}
		}
		return right - 1;
	}
}