[백준/Python] 2805번 : 나무 자르기

문제

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

풀이

https://nkdev.tistory.com/32

[백준/Java] 2805번 : 나무 자르기

1월에 풀었던 문제다. 이 때 이분탐색 문제를 많이 풀면서 감을 익혔는데 벌써 어려워지다니

풀이는 위 글과 같고 이번에 파이썬으로 풀면서 시간 초과가 떠서 좀 힘들었다. 

알고 보니 범위 조절하는 조건문 마다 avail_len(pc)를 호출해서 시간 초과가 발생한 것.. 이 부분을 고쳐줬다.

 

그리고 어려웠던 부분은 역시 이분탐색 결과로 뭘 리턴할지 정하는 부분이었다.

이미 문제를 성공한 친구는 start>end가 되기 전의 middle값을 전역 변수에 저장해서 구했다고 한다.

원래 방법으로는 start>end일 때 이전 middle값이 start인지 end인지 start-1인지.. 등을 시뮬레이션 해보고 리턴하면 된다.

 

그리고 또 어려웠던 부분은.. 범위 조절할 때 조건문을 M > total, M < total로 했는데 M > total, M <= total로 했어야 했다.

가져갈 수 있는 나무의 길이(total)가 M과 정확히 같은 경우도 고려해야 하기 때문이다.

코드

import sys

# 입력받기
N, M = map(int, sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))
result = 0

# 절단기 높이가 h일 때 가져갈 수 있는 나무 길이
def avail_len(h:int):
    ret = 0
    for i in range(0, len(trees)):
        l = trees[i]-h
        if l > 0: # len이 양수일 때만 누적
            ret += l
    return ret

# (1~가장 큰 나무 높이) 중에 H값을 이분 탐색으로 찾기
pl = 0
pr = max(trees)

while pl <= pr:
    pc = (pl+pr)//2 # 현재 탐색 중인 높이
    total = avail_len(pc)
    if M > total:
        pr = pc - 1
    elif M <= total:
        pl = pc + 1
        result = pc


print(result)