[백준 2805번] 나무 자르기

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

2805번: 나무 자르기

---

문제 접근 및 해결 방법

구해야 하는 값을 알고 있다. 이는 구해야 하는 값에 근접하기 위해 유추하는 과정이 필요하다. 이에 따라 이분 탐색을 이용하여 문제를 풀어보았다.

Python 시간초과! pypy3로 바꿔 제출했더니 통과되었다. Python 으로 풀 수 있는 방법은 없을까?..

---

import sys
n, length = map(int, sys.stdin.readline().strip().split())
trees = list(map(int, sys.stdin.readline().strip().split()))
answer = 0
# left 는 자를 수 있는 최소 높이
# right 는 자를 수 있는 최대 높이
left, right = 0, max(trees)
while left <= right:
    total = 0
    mid = (left + right) // 2
    for tree in trees:
        # 나무가 mid 값보다 클 때 자른다
        total += tree - mid if mid < tree else 0
    # 자른 총 나무길이가 가져가야할 나무길이보다 적을 때
    # 잘라서 나오는 총 나무길이를 늘려주기 위해 자르는 나무 길이를 줄여야 한다
    # right 를 mid - 1로 줄인다.
    if total < length:
        right = mid - 1
        continue
    # 목표는 주어진 나무길이를 구할 수 있는 '제일 긴' 나무길이를 구해야한다.
    # 이에 따라 answer 가 mid 보다 작으면 answer 에 mid 값을 할당한다.
    answer = mid if answer < mid else answer
    # 자른 총 나무길이가 가져가야할 나무길이보다 많기 때문에
    # 잘라서 나오는 총 나무길이를 줄여주기 위해 자르는 나무 길이를 늘려야 한다.
    # left 를 mid + 1로 증가시킨다.
    left = mid + 1
print(answer)