BOJ 2805: 나무 자르기 [Python 3]

오늘의 문제!

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

2805번: 나무 자르기

위 그림처럼 나무를 일정한 높이로 자르고, 윗 부분을 가지고 사용한다.

---

코드

n,m=map(int,input().split())
data=list(map(int,input().split()))
data.sort()
low=0
high=data[-1]
answer=0
while low<=high:
    mid=(low+high)//2
    num=0
    for i in range(len(data)):
        if mid<data[i]:
            num+=(data[i]-mid)
    if num<m:
        high=mid-1
    else:
        answer=mid
        low=mid+1
print(answer)

물론 2중 반복문을 통해서 구해도 되겠지만, 시간제한이 1초인데 나무의 개수는 백만개, 나무의 높이는 20억까지 커질 수 있기에 시간이 너무 오래 걸린다.

그래서 binary search를 통해 구현했다.

높이 0부터 제일 높은 나무의 높이 중에,

계속 반으로 나눠서 범위를 좁혀가서 가능한 수를 정한다.

 

하지만 answer가 나온다고 바로 break 하면 안 된다.

높이의 '최댓값'을 구하는 프로그램이기에, 만약 조건을 만족 하더라도 나무를 덜 벨 수 있으면 덜 벨 수 있도록 해야하지만,

예를 들어 16의 나무가 필요해도 어쩔 수 없이 17를 베는 게 최선일 수도 있다.

그렇기에 "자른 나무의 길이가" '필요한 나무의 양보다 많을 때' 우선 정답에 넣는다.

 

이렇게까지 이분 탐색이 유용하게 쓰일 줄 몰랐는데, 계속적으로 사용되는 알고리즘인 것 같다.