<aside> 🔥 백준 2805번 링크

</aside>

<aside> 🔥 문제 정리

첫째줄에 나무의 수 n이 주어지고, 필요한 나무의 길이 m이 주어진다.

둘째줄에 n개의 나무의 길이가 주어진다.

절단기에 높이 h를 지정해야하는데 둘째줄에 주어진 나무의 한줄을 연속해서 잘라낸다.

여기서 절단기의 높이만큼 자른 나무만 가져갈 수 있는데 이 길이가 m인 경우의 최대 수를 구하라.

</aside>

<aside> 🔥 문제가 처음에 이해하기가 어렵다.

아래 그림과 같이 목재의 길이가 20 15 10 17 인 경우에 7의 나무를 얻고자하면

15로 잘라내야한다는 것이다.

</aside>

<aside> 🔥 접근 방법

목재절단기의 높이를 0 ~ 나무이 길이의 최대 로 지정한다.

이진 탐색으로 중간 지점을 목재절단기의 높이로 두고 잘라냈을 때 얻은 나무의 길이가 목표치보다 크면,

중간 지점을 높혀서 나무가 덜 자르게 한다.

반대로 얻은 나무의 길이가 목표치보다 작다면 중간지점을 낮춰서 나무가 더 많이 잘리게 한다.

</aside>

<aside> 🔥 코드 진행

(1) 입력값을 받아오고 low, high를 지정한다.

low는 0부터 high는 현재 나무들의 길이중 최대로 지정한다.

import sys

def input():
    return sys.stdin.readline().strip()

n, m = map(int, input().split())
li = list(map(int, input().split()))

lo = 0          # 0 부터
hi = max(li)    # 리스트에서 가장 큰값
result = 0      # 결과값

(2) low가 high보다 높아지지 않는 선에서 반복문을 실행한다.

모든 나무의 길이가 들어있는 리스트를 순회하며 중간값으로 자르고 얻은 나무의 길이를

total에 저장한다.

while lo <= hi:
    total = 0               # 나무 자른 총 양
    mid = (lo + hi) // 2    # 중간 값

    # 리스트를 순회한다.
    for x in li:
        # 중간값으로 잘랐을때 잘려나간 나무들
        if x > mid:
            # 총 양에 잘려나간 길이 넣기
            total += x - mid

(3) 위에서 얻은 total의 양과 목표치를 비교해준다.

목표치보다 적게 얻었다면 중간지점을 낮춰서 더 잘라야하므로 왼쪽으로 탐색한다.

반대로 목표치보다 크게 얻었으면 중간지점을 높혀줘 오른쪽으로 탐색한다.

while lo <= hi:
    ...

    # 총 나무의 양이 목표치보다 작으면
    # 왼쪽으로 탐색해서 더 짧게 자르기
    if total < m :
        hi = mid - 1
    # 총 나무의 양이 목표치보다 크면
    # 오른쪽으로 탐색해서 더 길게 자르기
    else :
        result = mid
        lo = mid + 1

</aside>