[백준] 2805 | 나무 자르기 [파이썬/python]

문제

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

M미터의 나무를 얻기 위해 절단기에 설정할 높이의 최댓값을 구하는 문제이다.

 

접근

요즘은 코드가 지저분해지더라도 일단 작성하고, 그 이후 최적화하는 식으로 백준 문제를 풀고 있다.
처음에는 이 문제를 DP와 비슷한 방식으로 접근하려고 했는데, 그렇게 코드를 작성해 보니 너무나도 비효율적인 코드가 만들어졌다. (높이마다 잘리는 나무 개수를 리스트에 저장하도록 구현했다.) 코드를 돌려보지 않더라도 이 답안을 제출했다간 시간 초과가 뜰 것이라는 사실을 알 수 있었다. 그래서 이분 탐색으로 다시 접근했다.

 

코드

N, M = map(int, input().split())
trees = list(map(int, input().split()))
s = 0
e = max(trees)
h = 0

while s <= e:
    m = (s + e)//2
    tmp = sum((t - m) if t - m > 0 else 0 for t in trees)
    if tmp >= M:
        h = m
        s = m+1
    else:
        e = m-1
        
print(h)