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

---

문제

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

---

문제풀이(시간초과)

# 시간초과

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

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

hap = 0

tree.sort()

max = tree[n-1]

while hap < m:

    hap = 0

    max -= 1

    for i in range(n):

        if tree[i] - max >= 0:

            hap += tree[i] - max

print(max)

 

처음 이 문제를 접했을 때는 나름 풀만하다고 생각해서 내 나름대로 반복문으로 풀어보았다.

혼자서 이것 저것 고치면서 풀고 난 후 백준에 답을 제출했는데 시간초과

 

시간초과를 해결할 방법은 이진탐색이었다. 

---

문제풀이(정답) : 이진탐색

# 이분탐색

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

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

start = 0

end = max(tree)

result = 0

while start <= end:

    mid = (start + end) // 2

    hap = sum(max(0, x - mid) for x in tree)

    if hap >= m:

        result = mid

        start = mid + 1

    else:

        end = mid - 1

print(result)

 

※ 이진탐색이란?

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

 

따라서 시작점과 끝점, 중간점을 이용하여 문제를 풀었다.

 

tree의 합도 위에서와 다르게 한 줄로 깔끔하게 작성했다.

hap = sum(max(0, x - mid) for x in tree)
0보다 클 때만 합을 더한다는 코드를 max(0, 값)으로 사용했다.