[파이썬] 백준 2805 : 나무 자르기

[파이썬] 백준 2805 : 나무 자르기

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

2805번: 나무 자르기

실버3

이분탐색, 매개변수 탐색

---

코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
hlst = list(map(int, input().split()))

ps = 1
pl = max(hlst)
while ps <= pl:
    pc = (ps + pl) // 2
    summ = sum([i-pc if pc < i else 0 for i in hlst])
    if summ >= M:
        ps = pc + 1
    else:
        pl = pc - 1
print(pl)

 

이분탐색으로 최댓값을 구하는 문제.

나무를 가져갈 양을 최대한 적게 하려면 나무를 자르는 높이가 최대한 높아야 한다.

따라서 pl값을 출력하도록 한다.

 

잘라낸 나무 길이의 합인 summ이 M보다 크거나 같은 것은 나무를 필요 이상으로 많이 잘라낸 것이므로 자르는 높이를 더 높여야 할 필요가 있다. 따라서 ps 값을 더 상향 조정한다.

 

 

중간에 summ = sum([i-pc if pc < i else 0 for i in hlst]) 부분은 원래

for i in hlst:
        if i >= pc:
            summ += (i - pc)

였었는데 시간 초과가 났다. (근데 pypy3로 제출하면 정답)

 

이걸

summ = sum([i-pc if pc < i else 0 for i in hlst])

형태로 바꾸니까 python3에서도 정답으로 제출되었다.

이렇게 축약하는 방식을 리스트 내포(List Comprehension)이라고 한다.

그냥 for문으로 돌리는 것보다 성능이 좋다고 한다.

간결한 표현은 좋은데 구현해야할 식이 복잡하면 가독성이 떨어지는 단점이 있다.