[백준] 2805. 나무 자르기

문제

백준 2805. 나무 자르기  https://www.acmicpc.net/problem/2805

 

코드

n, m = map(int, input().split())
forest = list(map(int, input().split()))
s = 1
e = max(forest)

while s <= e:   # 교차되기 전까지
    mid = (s+e) // 2

    # 얼마나 나무를 모았는가?
    wood = 0
    for tree in forest:
        if tree >= mid:
            wood += tree - mid

    # 업?
    if wood >= m:
        s = mid + 1
    # 다운?
    else:
        e = mid - 1

print(e)

• 완전 탐색으로 모든 H 값을 다 확인하기엔 시간 초과가 나므로, 이분 탐색을 사용해야 한다.
• H(절단기 높이)를 이분 탐색하며, 현재 높이로 나무를 자르면 m만큼 얻을 수 있는지를 판단한다.

 

 

풀이

n, m = map(int, input().split())
forest = list(map(int, input().split()))
s = 1  # 최소 자를 수 있는 높이
e = max(forest)  # 최대 자를 수 있는 높이

입력받기 및 초기값을 설정한다.

• n: 나무의 수
• m: 가져가야 하는 최소 나무 길이
• forest: 나무들의 높이 리스트
• 이분 탐색을 위해 s, e를 설정 (높이의 범위)

 

while s <= e:
    mid = (s + e) // 2  # 절단기 높이 후보

이분 탐색을 시작한다.

• mid : 현재 탐색 중인 절단기 높이
• 이 높이로 자를 때 나무를 얼마나 얻을 수 있는지 확인한다.

 

    wood = 0
    for tree in forest:
        if tree >= mid:
            wood += tree - mid  # 자른 만큼만 더함

나무의 길이를 계산한다.

• 각 나무가 mid보다 크면 잘리기 때문에 잘린 길이를 더해준다.
• 전체 잘린 나무의 총합을 wood로 저장한다.

 

    if wood >= m:
        s = mid + 1  # 충분히 얻었으니 더 높게 잘라보기
    else:
        e = mid - 1  # 부족하니까 낮춰야 함

이분 탐색 조건을 설정한다.

• 나무를 충분히 얻었다면 (wood >= m) 절단기 높이를 더 높일 수 있으므로 s = mid + 1
• 부족했다면 높이를 낮춰야 하므로 e = mid - 1

 

print(e)

최종 결과를 출력한다.

• 최종적으로 절단기 높이의 최대값은 e에 저장된다.
• s > e가 되었을 때, e가 유효한 마지막 절단기 높이이다.

 

 

 

💡 이 문제는 "최댓값을 구하라"는 말에서 이분 탐색의 힌트를 얻을 수 있다.

💡 어떤 조건을 만족하는 최고의 값을 구할 때는 이분 탐색을 떠올릴 수 있다.