백준 문제풀이 - 2805 번

링크 -> https://www.acmicpc.net/problem/2805

1. 요약 및 풀이방법

절단기를 이용해 한줄의 나무를 동일한 높이로 자를 때,
총 합 길이 M이상을 자를 수 있는 최선의 높이를 찾는 문제입니다.

이전에 풀었던 랜선 자르기 문제와 유사합니다.

이분 탐색 알고리즘을 이용해 특정 높이 H로 잘랐을 때,
필요한 길이 M보다 작다면, H보다 낮게 해서 더 많은 나무를 잘라야 하므로, H보다 큰 범위는 볼 필요가 없습니다.
반대로 필요한 길이 M보다 크면, 이미 필요한 범위는 넘겼으므로 절단기 높이를 올려 최소한의 나무만 잘라냅니다.

2. Code

import sys

def main():
    N, M = map(int, input().split())
    trees = list(map(int, sys.stdin.readline().rstrip().split()))

    start = 0
    end = max(trees)
    while start <= end:
        mid = (start + end) // 2
        sums = 0
        for tree in trees:
            if tree > mid:
                sums += tree - mid
        if sums < M:
            end = mid - 1
        else:
            start = mid + 1
    print(end)

if __name__ == "__main__":
    main()

3. 학습 내용

원래 while 안의 반복문은 다음과 같은 코드였는데,
모든 경우 max 함수를 취하다 보니 시간 초과가 되어 조건문을 이용하도록 수정했습니다.

        for tree in trees:
            max(tree-mid, 0)

4. 결과