Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

21. 이분 탐색

이분 탐색 알고리즘을 배워 봅시다.

Java / Python

4. 나무 자르기

2805번

이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 문제 2

이번 문제는 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하는 문제입니다.

• Java

import java.util.Scanner;

public class Main {
	static int N;
	static int M;
	static int[] tree;
	static long max = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        
		N = sc.nextInt();
		M = sc.nextInt();
		tree = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			tree[i] = sc.nextInt();
			max = Math.max(max, tree[i]);
		}

		long start = 0; 
		long end = max;
		while (start <= end) {
			long mid = (start + end) / 2;
			long sum = 0;
            
			for (int t : tree) { 
				if (t > mid)
					sum += t - mid;
			}
			if (sum >= M) { 
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		System.out.println(end);
	}
}

• Python

시간 초과가 나서 pypy3로 실행했습니다.

import sys
N, M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
start, end = 1, max(tree) # 이분탐색 위치

while start <= end: 
    mid = (start + end) // 2 
   
    log = 0 # 벌목된 나무의 총합
    for t in tree:
        if t >= mid:
            log += t - mid      
    if log >= M:
        start = mid + 1
    else:
        end = mid - 1
print(end)