백준 2805 - 나무 자르기

문제

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

2805번: 나무 자르기

 

 

풀이

 

나무 높이의 범위가 엄청 넓으므로 이분 탐색을 통해 절단기의 높이를 정한다. 절단기의 최소 높이는 0이고 최대 높이는 나무들 중에 최대값과 같다. 이 사이에서 절단기의 높이를 찾으면 된다.

이분 탐색을 이용하므로 중간점을 절단기의 높이로 설정하면서 문제 조건 M을 만족하는지 확인한다.

 

1. 만약 중간점으로 잘랐을 때 가져가는 나무의 길이가 M보다 같거나 크면 (mid + 1, end) 까지 다시 이분 탐색을 진행한다.

이 때는 가져가는 나무의 길이가 M보다 크므로 문제 조건을 만족하고, 이 때 mid 값을 답으로 저장한다.

2. 만약 중간점으로 잘랐을 때 가져가는 나무의 길이가 M보다 작으면 (start, mid - 1)까지 다시 이분 탐색을 진행한다.

 

위 과정을 반복하여 답을 구할 수 있다.

 

 

코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] st = br.readLine().split(" ");
 
        int n = Integer.parseInt(st[0]);
        int m = Integer.parseInt(st[1]);
 
        int[] array = new int[n];
        st = br.readLine().split(" ");
        int index = 0;
        for (String s : st) {
            array[index++] = Integer.parseInt(s);
        }
        Arrays.sort(array);
        int left = 0;
        int right = array[n-1];
 
        int result = 0;
        while (left <= right) {
            long sum = 0;
            int mid = (left + right) / 2;
 
            for (int num : array) {
                if (num > mid) {
                    sum += num - mid;
                }
            }
 
            if (sum >= m) {
                left = mid + 1;
                result = mid;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(result);
        br.close();
    }
 
}
 

 

python

n, m = map(int, input().split(' '))
array = list(map(int, input().split()))
 
start = 0
end = max(array)
 
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array:
        if x > mid:
            total += x - mid
    if total < m:
        end = mid - 1
    else:
        result = mid 
        start = mid + 1
 
print(result)