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

2023/7/16

실버2

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

2805번: 나무 자르기

 

 

🔎 분석

이분탐색 문제를 풀려고 선택한 문제. 이분탐색을 적용하면 되는 단순한 문제였다.

이분탐색 없이 그냥 접근하면 시간초과가 뜬다.

재귀로 이분탐색을 적용하고 예제를 돌렸는데, 이상하게 return값이 제대로 안 나왔다. 이유는 아직도 모르겠다 ㅠ 그래서 그냥 print 하도록 하여서 맞았습니다가 나왔다.

그리고 numpy 라이브러리를 썼더니 런타임에러(not find module)가 나왔다 !! 주의하자.

 

 

📍TIP

시간이 2132ms가 나와서 좀 줄여보고자 재귀 대신 while문을 사용했는데, 그랬더니 오히려 4856ms로 2배 가량의 시간이 나왔다.

재귀가 while문보다 빠른 것 같다.

 

💻 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
tree_heights = list(map(int, input().split()))
H = 0
tree_heights = sorted(tree_heights)

def binary_search(a, l, r, M):
    mid = (l+r)//2

    if l<=r:
        sum_ = 0
        for tree in a:
            if tree>mid:
                sum_ += tree-mid

        if sum_ < M:
            binary_search(a, l, mid-1, M)
        elif sum_ >= M:
            binary_search(a, mid+1, r, M)
    else:
        print(mid)
        return mid

result_height = binary_search(tree_heights, 0, max(tree_heights), M)