백준 / 나무 자르기 / 2805번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 나무 자르기 / 2805번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/2805

 

문제 설명

---

나의 풀이

def binary_search(tree, m):
    # 결과 값
    answer = 0
    # 이진 탐색을 위한 변수
    left = 0
    right = max(tree)

    # 경우의 수
    while left <= right:
        # 나무를 자른 결과 값
        total = 0

        # 자르는 높이의 길이의 중간 지점
        slice_high = (left + right) // 2

        # 나무 잘라서 total에 대입
        for t in tree:
            if t > slice_high:
                total += t - slice_high

        # 자른 나무의 길이가 길면 높여야 한다.
        if total < m:
            right = slice_high - 1
        # 나무의 양이 충분하다면 result에 저장 밑 오른쪽 부분 탐색
        else:
            answer = slice_high
            left = slice_high + 1

    return answer


def main():
    # 나무의 수 N과 나무의 길이 M이 주어진다.
    n, m = map(int, input().split())
    # 나무
    tree = list(map(int, input().split()))

    print(binary_search(tree, m))


main()

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/188

[알고리즘] 이분 탐색(Binary Search)