2805 나무 자르기

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read =sys.stdin.readline

N,M = map(int,read().split())
trees = list(map(int,read().split()))

# 이진 탐색을 위해 정렬
trees.sort()

# M을 맞추기 위해 노력하자
start = 0
end = max(trees)

while (start<=end):
    H = (start+end)//2
    meters = 0

    for tree in trees:
        if tree - H > 0 :
            meters += ( tree - H)

    if meters >= M : # 너무 많이 잘랐으면, H를 좀더 키우자
        start = H+1

    else : # 너무 적게 잘랐으면 H를 줄이자.
        end = H-1

print(end)

3. 문제 풀이

이 문제는 함수를 안만들고 그냥 while문을 써서 하지만, 본질은 똑같다. 단지 재귀를 썼냐, 반복문을 썼냐의 차이인데, 근데 이게 생각보다 금방 익혀지지가 않는다. 많이 반복하면서 외우도록 하자.

python으론 시간초과이고 pypy3는 통과한다.