문제

' 2805번 나무자르기 '
https://www.acmicpc.net/problem/2805

Check point

📌 이진 탐색/ 이분 탐색/ binary search

• 자료의 중앙에 있는 원소를 고른다.
• 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
• 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
• 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

기본 코드

💡 반복문 사용

def binary(arr, key):
    start, end = 0, len(arr) - 1
    while start <= end:
        middle = (start + end) // 2
        if arr[middle] == key:  # 검색 성공
            return True
        elif arr[middle] > key:
            end = middle - 1
        else:
            start = middle + 1
    return False  # 검색 실패

💡 재귀 사용

def binary(arr, start, end, key):
    if start > end:  # 검색 실패
        return False
    else:
        middle = (start + end) // 2
        if arr[middle] == key:  # 검색 성공
            return True
        elif arr[middle] > key:
            binary(arr, start, middle - 1, key)
        elif arr[middle] < key:
            binary(arr, middle + 1, end, key)

📌 문제 조건

• 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하여야 하므로 total >= M 인 값은 모두 고려해야 한다.

코드

python

💡 반복문 사용

N, M = map(int, input().split())
h = list(map(int, input().split()))
start, end = 1, max(h)  # 1을 시작, 최댓값을 끝
result = 0  # 출력해야 하는 절단기 높이
while start <= end:  # 반복문 종료 조건
    mid = (start + end) // 2  # 중앙 원소 고르기
    total = 0  # 잘린 나무 높이 총합
    for H in h:
        if H > mid:  # 나무 높이가 절단기 높이 보다 커야 잘림
            total += H - mid
    if total >= M:
        result = mid # 절단기 높이 = 중앙값
        start = mid + 1  # 잘린 나무 높이 총함이 M이상 이면 중앙값+1 ~ 끝 값 다시 찾기
    else:
        end = mid - 1  # 잘린 나무 높이 총함이 M미만 이면 시작 ~ 중앙값-1 값 다시 찾기
print(result)

다른 방법

💡 재귀 사용

def binary(h, start, end, M):
    global result
    if start > end:
        return
    mid = (start + end) // 2
    total = 0
    for H in h:
        if H > mid:  
            total += H - mid
    if total >= M:
        result = mid  
        return binary(h, mid + 1, end, M)
    else:
        return binary(h, start, mid - 1, M)


N, M = map(int, input().split())
h = list(map(int, input().split()))
start, end = 1, max(h)  
result = 0  
binary(h, start, end, M)
print(result)