[Python] 백준 #2805- 나무 자르기

문제

---

2805번: 나무 자르기

코드

---

My answer

import sys
from bisect import bisect_left
input=sys.stdin.readline

n,m=map(int,input().split())
tree=list(map(int,input().split()))

def binary_search(start,end):
    
    if(start>end):
        return end
    
    mid=(start+end)//2
    
    tmp=[i-mid for i in tree if i>mid]
    tmp=sum(tmp)
    #print(start, end ,mid, tmp)
    
    if(tmp==m):
        return mid
    elif(tmp<m):
        return binary_search(start,mid-1)
    else:
        return binary_search(mid+1,end)

print(binary_search(0,max(tree)))

Another answer

N, M = map(int, input().split())
tree = list(map(int, input().split()))
start, end = 1, max(tree) #이분탐색 검색 범위 설정

while start <= end: #적절한 벌목 높이를 찾는 알고리즘
    mid = (start+end) // 2
    
    log = 0 #벌목된 나무 총합
    for i in tree:
        if i >= mid:
            log += i - mid
    
    #벌목 높이를 이분탐색
    if log >= M:
        start = mid + 1
    else:
        end = mid - 1
print(end)

 

풀이

---

이 문제는 이전에 푼 [이것이 코딩 테스트다]의 "떡볶이 떡 자르기"와 아예 똑같은 문제였다.

이분탐색으로 구현하는 문제였고, 역시나 종료조건이 헷갈려서 여러번 써보고 해결했다. 원래 이분탐색이 마지막 종료조건을 정하는게 매우 중요한 것 같다. 이번 문제에선 최종적으로 end를 출력하는게 조건이었다. 

또한 나는 위 코드를 이용해서 시간초과나 메모리초과에 걸리지 않고 통과했지만, 

재귀를 이용해서 구현할 경우 함수가 호출될 때마다 호출 스택에 쌓이고 반환될 때마다 호출 스택에서 제거되는 것을 반복하기 때문에 반복문을 이용하여 구현하는 것이 더 빠르다고 한다. (재귀는 단순히 가독성?)

또한 자르고 난 나무들의 합을 구할 때도 데이터의 갯수가 많은 경우에는 파이썬의 내장함수 sum보다는 반복문을 이용해서 구하는 것이 더 빠르다고 한다.  
(이 호출 스택은 메모리의 스택 영역에 저장된다.)

아래에 백준 질문 게시판에 있는 다양한 반례랑, 이것이 코딩 테스트다의 떡볶이 떡 자르기, 이분탐색의 종료조건에 관한 글을 링크해뒀다.(이분탐색 종료조건 관련 글은 꼭 읽어보기)

 

글 읽기 - 반례 부탁드립니다

떡볶이 떡 만들기-[이것이 취업을 위한 코딩 테스트다]