[이분탐색] 백준 - 나무 자르기

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

2805번: 나무 자르기

 

-문제해설

 

1. 나무길이 입력값들을 받을 때 가장 큰 값을 max에 저장시킨다. 입력값들은 arr배열에 저장한다.

2. 이분탐색을 위해 start = 0, end = max로 설정한다.

3. while( start <= end )조건이 거짓이 될 때까지 반복한다.

 3-1. while문 안에는 mid = ( start + end ) / 2값을 설정한다.

 3-2. 나무길이 배열 arr를 순회하면서 값이 mid보다 큰 나무들에 대해서만 sum에 누적합한다.

 3-3. arr배열 순회가 끝나면 sum값과 m값을 비교해서 sum >= m이면 mid값이 너무 작아서 나무를 작게 짜른 것이므로

      나무를 크게 자르기 위해 start = mid + 1로 start값을 증가시킨다.

4. while문이 끝나면 문제에서 '적어도 가장 큰 톱 길이를 출력하라'라고 하였으므로 최종 end값을 출력시킨다.

 

 

 

-자바

package search;

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

public class BJ2805_1 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() );
		long m = Integer.parseInt( st.nextToken() );
		
		int[] arr = new int[n];
		int max = 0;
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<n; i++ ) {
			arr[i] = Integer.parseInt( st.nextToken() );
			max = Math.max( max, arr[i] );
		}
		
		long start = 0;
		long end = max;
		
		while( start <= end ) {
			long mid = (start + end) / 2;
			long sum = 0;
			
			for( int a : arr ) 
				if( a > mid ) sum += a - mid;
			
			if( sum >= m ) start = mid + 1;
			else end = mid - 1;
		}
		
		System.out.println( end );
	}
}

 

-파이썬( pypy3로 해야지 통과 )

import sys
l = sys.stdin.readline
n, m = map( int, l().split() )

arr = list( map(int, l().split()) )
start = 0
end = max( arr )

while start <= end:
    mid = (start+end)//2
    sum = 0
    
    for a in arr:
        if a > mid: sum += a - mid
        
    if sum >= m: start = mid + 1
    else: end = mid - 1
print( end )