백준 2805번 나무 자르기

NameError·2021년 5월 9일

오랜만에 다시 찾아본 이진탐색 문제 너무 어려웠다 ㅋㅋㅋ

문제 링크

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

풀이 전 계획과 생각

이 문제는 1654번 랜선 자르기와 비슷한 이진 탐색 문제라고 할 수 있다.
랜선 자르기 문제에서는 정수 나눗셈을 해서 가장 길게 자르는 랜선 길이를 찾는데 랜선을 많이 자른 것도 원하는 개수를 자른 것에 포함한다. 그래서 원하는 개수를 잘랐다고 해도(정수 나눗셈이니까) 더 긴 길이에서 성립할 수 있으니까 더 긴 길이에서 탐색을 계속하고, 원하는 개수보다 더 많이 잘린다고 해도 더 적게 자르는 값을 끝까지 못 찾을 수도 있으니까 일단 최댓값을 업데이트해둔 채로 탐색한다.

반면에 나무 자르기 문제는 자연수끼리의 뺄셈 결과의 합이다. 딱 맞는 값이 나왔다면 더 큰 값에서 원하는 결과가 나올 수 없고 당연히 더 큰 값에서는 잘리는 나무의 양이 줄어들기 때문에 탐색을 계속할 필요가 없어서 탐색을 종료한다. 그러나 나무의 양이 더 많게 나왔다면 (H에서 1만 늘려도 나무의 양은 1이 줄어드는 게 아니라 나무의 개수만큼 줄어들 수 있다) 더 큰 H 값에서 원하는 나무의 양이 나오지 않을 수 있기 때문에 일단 최댓값을 업데이트한
채로 탐색을 계속해야 한다.

구하려는 H의 최댓값은 안 자르고 남기는 나무의 키이다. 예를 들어 나무의 키가 1과 10이 있는데 H가 6이면 첫번째 나무는 잘리지 않고 두번째 나무만 끝에서 4가 잘려서 목재의 양은 4가 된다.

그러므로 잘린 나무의 양이 적다면 더 작은 H 중에서 탐색해야 하고 잘린 나무의 양이 많다면 더 큰 H 중에서 탐색해야 한다.

H의 최댓값은 당연히 나무의 키의 최댓값이나(여기에서 목재의 양은 0이겠지) 최댓값-M//N(여기서는 제일 큰 나무가 다른 나무들과 키가 같다면 모두 똑같이 자르면서 여기에서 H가 확정되고 다른 나무들이 작아서 목재가 모자란다면 H를 줄이면서 탐색해야 할 것이다)을 하면 될 것 같고 최솟값은 다음 중 최댓값으로 해보았다.

제일 큰 나무의 키-M: 일단 제일 큰 나무 하나에서만 원하는 목재가 모두 확보된다. 나머지 나무들이 이보다 작다면 그 나무들은 잘리지 않을 것이고 나머지 나무들이 이보다 커서 확보되는 목재의 양이 많아진다면 H를 더 늘려가면서 탐색할 수 있다.
제일 작은 나무의 키-(M//N)-1: 만약에 각각의 나무를 똑같이 자를 수 있다면 정수 나눗셈의 결과인 M//N+1만큼 자르면 M보다 크거나 같은 값을 얻을 수 있다. 정수 나눗셈이라서 소숫점 이하는 버려지기 때문에 1을 더한 것이다. 만약에 제일 작은 나무와 다른 나무들의 키 차이가 없다면 원하는 목재의 양이 이 H값에서 정해질 것이고, 만약에 다른 나무들의 키가 크다면 목재의 양이 훨씬 많아지기 때문에 더 큰 H값에서 탐색을 계속할 수 있다.
0: 물론 앞의 정수 뺄셈들의 결과가 0보다 작다면 H는 당연히 0 이상이어야 한다.

풀이 (코드 블록 첨부)

# 백준 2805번 나무 자르기 

import sys
def timber(arr,L):
    trees=0
    for unit in arr:
        trees+=(unit-L if unit-L>0 else 0)
    return trees



def BinarySearchT(k_min, k_max, key,arr,current_max):
    
    if k_min<=k_max:        
        mid=(k_min+k_max)//2
        if timber(arr,mid)==key:
            #if mid>current_max:
            #    current_max=mid
            #return BinarySearchT(mid+1, k_max,key,arr,current_max)
            return mid
        elif timber(arr,mid)<key:          
            return BinarySearchT(k_min, mid-1,key,arr,current_max)
        else:
            if mid>current_max:
                current_max=mid
            return BinarySearchT(mid+1, k_max,key,arr,current_max)
    else:
        return current_max
'''    
def BinarySearch(k_min, k_max, key,arr):
    current_max=0
    while k_min<=k_max:
        mid=(k_min+k_max)//2
        if timber(arr,mid)==key:
            return mid
        elif timber(arr,mid)<key:
            k_max=mid-1
        else:
            if current_max<mid:
                current_max=mid
            k_min=mid+1
    return current_max
'''    


    
    
N,M=map(int,sys.stdin.readline().split())

trees=list(map(int,sys.stdin.readline().split()))
#print(trees)

max_tree=max(trees)
min_tree=min(trees)
#print(BinarySearchT(max(cutter-M,0), cutter, M ,trees,0))

print(BinarySearchT(max(max_tree-M,0,min_tree-(M//N)-1), max_tree-(M//N), M ,trees,0))