[BAEKJOON] 2805 나무 자르기

문제 요약

• 알고리즘 분류: 이진 탐색, 수학
• 난이도: Silver3
• 문제내용:
  •  

• 사이트: https://www.acmicpc.net/problem/2805

문제풀이

 

Code

Python

n, m = map(int, input().split())
trees = list(map(int, input().split()))
min_value = 1
max_value = max(trees)
while min_value <= max_value:
    mid = (min_value + max_value) // 2
    lenth = sum([tree- mid for tree in trees if tree > mid])
    if m > lenth: 
        max_value = mid - 1
    else:
        min_value = mid + 1
print(max_value)

Java

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

public class Main {



	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		// 나무 최대 크기가 2,000,000,000인것과 N개
		long M = Integer.parseInt(st.nextToken());
		long[] trees = new long[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			trees[i] = Long.parseLong(st.nextToken());
		}
		long start = 1l;
		long end = Arrays.stream(trees).max().getAsLong();
		while (start <= end){
			long mid = (start + end) / 2;
			long cutTree = 0;
			for (int i = 0; i < N; i++) {
				cutTree += trees[i] < mid? 0 : trees[i] - mid;
			}
			if(cutTree < M){
				end = mid - 1;
			}else{
				start = mid + 1;
			}
		}

		System.out.println(end);
	}
}