Baekjoon 2805번 나무 자르기

문제

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

걸린 시간

00 : 48 : 49

풀이

import sys
input = sys.stdin.readline

def Cut(tree, mid):
    remain = 0

    for i in tree:
        if i > mid:
            remain += i - mid

    return remain

if __name__ == "__main__":
    # N : 나무의 수 M : 집으로 가져가려는 나무의 길이
    N, M = map(int, input().split())

    # 나무의 높이
    tree = list(map(int, input().split()))

    left = 0
    right = max(tree)

    while left <= right:
        # mid : 절단기에 들어갈 수 있는 높이의 최댓값
        mid = (left + right) // 2

        remain = Cut(tree, mid)

        if remain >= M:
            result = mid
            left = mid + 1
        else:
            right = mid - 1

    print(result)

1654번 랜선 자르기 문제와 동일한 이분 탐색 문제이다.

while 문 속의 for 문을 함수로 처리해야만 Python3 언어로 제출을 할 때 통과할 수 있는 원인 모를 문제가 있다. 메모리 효율은 떨어지지만 수행속도가 빠른 pypy3 언어로 제출을 하면 함수로 처리하지 않아도 통과가 된다.

input() 보다 빠른 sys 모듈의 sys.stdin.readline() 사용은 해당 문제 통과에 크게 영향을 주지 않는다.