📚 2805 - 나무 자르기

나무 자르기

이해

벌목나무, 벌목 높이를 움직여 필요 나무 길이를 채우는지 보는 것!

1) 가장 짧은 길이 1을 start로, 나무 중 가장 긴 길이를 end로 둔다.
2) 이분탐색이 끝날 때까지 while 문을 돌린다.
3) mid를 start와 end의 중간으로 두고, 모든 값에서 mid를 빼 총 어느정도 길이의 벌목된 나무가 나오나 살펴본다.
4)

• 벌목나무가 목표치 이상이면 mid + 1을 start로 두고 다시 while문을 반복한다.
• 벌목나무가 목표치 이하라면 mid - 1을 end로 두고 다시 while문을 반복한다.

5) start와 end가 같아지면, 조건을 만족하는 최대의 나무 절단 높이를 찾으면 탈출한다.

소스

import sys

read = sys.stdin.readline

n, m = map(int, read().split())

arr = list(map(int, read().split()))

start, end = 1, max(arr)  # 이분 탐색 검색 범위 설정

while start <= end:
    # print("start, end : ", start, end, end=" ")
    mid = (start + end) // 2
    find_m = 0

    for i in arr:
        if i > mid:
            find_m += (i - mid)


    # 발목 높이 m보다 크거나 같다면 start를 늘린다.
    # 발목 높이 m보다 작다면 end를 줄인다.

    if find_m >= m:
        start = mid + 1
    else:
        end = mid - 1

    # print("mid : ",mid)

print(end)

채점 결과

참고 : https://claude-u.tistory.com/446