[BOJ 2805] 나무 자르기(Python)

문제링크

나무 자르기

풀이 전 계획 및 생각

left를 0, right를 나무의 최대 길이로 설정하고 자르는 길이를 이분 탐색으로 찾을 생각을 했다.
잘린 나무들의 길이의 합이 m보다 크다면 톱날의 높이를 지금보다 높일 수 있다는 의미이므로 이분탐색을 더 진행했다.
잘린 나무들의 길이의 합이 m보다 작은 경우에는 그보다 톱날이 높은 경우는 어떻게하더라도 m보다 큰 길이를 얻을 수 없기 때문에 right를 줄여서 탐색을 계속했다.
그리고 left가 right와 커지면 안된다고 가정하고 이분 탐색을 진행했기 때문에, 탈출 조건으로 걸어주었다.

풀이

import sys

n, m = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().rstrip().split()))

left, right = 0, max(array)
answer = 0
while left <= right:
    mid = (left + right) // 2
    hap = 0

    hap = sum([i-mid if mid < i else 0 for i in array])

    if hap >= m:
        answer = mid
        left = mid+1
    else:
        right = mid-1

print(answer)

풀이하면서 막혔던 점과 고민했던 점

이분 탐색으로 접근하기만하면 될 것 같았는데 생각보다 시간 초과가 해결되지않아서 정말 막막했었다.
따로 함수로도 빼보고했는데 시간 초과가 발생했다.
이분 탐색에는 문제가 없다는 확신을 가지고 잘린 나무 길이의 합을 구하는 부분에서 속도를 줄이기 위해서 구글링을 해본 결과 sum([i-mid if mid < i else 0 for i in array])와 같이 구현하는 방식을 얻을 수 있었다.
아마도 내장함수를 사용하면 cpython이다 보니 python 으로 하나하나 더하는 것보다 속도가 월등하게 빠른 것 같다.(본인의 추측일 뿐입니다.)

풀이 후 알게된 개념과 소감

내장 함수를 잘 활용하는 것도 중요하다는 생각을 했다.