[백준] 2805. 나무 자르기 (Python)

백준 문제 풀이 - 이진탐색

📰 문제

문제 확인 🏃

💡 입출력 예제

4 7
20 15 10 17

>> 15

5 20
4 42 40 26 46

>> 36

💬 풀이

🎵 첫번째 풀이

import sys

input = sys.stdin.readline
N, M = map(int, input().split())            # 나무의 수 N, 가져가려는 나무의 길이 M
trees = list(map(int, input().split()))     # 나무들의 높이


def solution(start, end):
    answer = 0

    while start <= end:
        mid = (start + end) // 2

        total = 0
        for t in trees:
            if t > mid:
                total += (t - mid)

        if total < M:
            end = mid - 1
        else:
            answer = mid
            start = mid + 1

    return answer

print(solution(0, max(trees)))

🎵 두번째 풀이

import sys

input = sys.stdin.readline
N, M = map(int, input().split())            # 나무의 수 N, 가져가려는 나무의 길이 M
trees = list(map(int, input().split()))     # 나무들의 높이


def solution(start, end):
    answer = 0

    while start <= end:
        mid = (start + end) // 2

        total = sum([t - mid for t in trees if t > mid])

        if total == M:
            return mid
        elif total < M:
            end = mid - 1
        else:
            answer = mid
            start = mid + 1

    return answer

print(solution(0, max(trees)))

✒️ 생각