백준 알고리즘 - 나무 자르기 (번호) [Python]

 

 

 문제

 

www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

 

 

 

 

 

 문제 상황

 

- 주어진 나무 리스트를 기준 길이로 자를 때, 주어진 길이 M 이상 만큼의 길이를 얻을 수 있는 경우 가능한 최대 높이를 구한다.

 

 

 

 

 

 

 해결 전략

 

- 이분탐색을 이용하여 기준 길이를 움직이며 구한다. 기준 길이를 구할 때 linear하게 검색할 경우 너무 많은 탐색이 있으므로 logN의 이분 탐색이 필요하다.

 

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
N_list = list(map(int, input().split()))
top = 0 # 나무 길이중 최대값
for i in range(N):
    if N_list[i] > top : top = N_list[i]
bot = 0 # 아래 기준선
def cutting(check):
    length = 0 # 얻을 수 있는 나뭇가지의 길이
    for i in range(N):
        if N_list[i] > check: length += (N_list[i]-check)
    if length >= M: return True
    return False
while top >= bot:
    mid = (top+bot)//2
    if cutting(mid): bot = mid+1
    else: top = mid-1
print(top)

 

 

 

 

 

 

 

 

 해설

 

- 톱의 높이를 이분 탐색하며 원하는 길이 이상의 나뭇가지가 나올 경우 하한선을 올리고, 안될 경우는 상한선을 내리는 작업을 반복한다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 이분 탐색의 경우 이미 판단한 값을 다시 연산할 이유가 없으므로 mid+1, mid-1 해주고, 연산이 종료되는 기준을 역전이 일어날 때로 잡았다. 

 

- 백준은 pypy3로 코드를 넘겨야 훨씬 빠르다. 완전히 같은 코드도 python3로 해서 안되다가 pypy3로 해서 모두 통과하였다.