스파르탄 365 5주차 (3) 나무 자르기

참고사이트: 나무 자르기 참고

5주차

백준 2805번 나무 자르기

문제링크 : https://www.acmicpc.net/problem/2805

💡 풀이 중 고민

• middle 값 찾고
• N개의 나무에서 뺀값을 더해서 (음수면 포함)
• M과 비교 후 맞으면 출력

--> 틀림

    if sum == M:
        print(mid)
        break
    elif sum > M:
        left = mid + 1

    else:
        right = mid - 1

? 위처럼 중간값을 왔다갔다하는 과정에서 답이 나오지 않는 경우를 발견했다.

! 해결 방법

! 조건을 만족하는 최대의 나무 절단 높이를 찾으면 탈출한다. 조건을 보면, M과 딱 일치하지 않는 경우가 생김을 파악할 수 있다. 그러므로 mid값이 아닌 right값을 출력해야하고,
left 변화 또한 sum>=M인 경우 모두 이루어져야 한다.

!! 스킬

.

깨달음

• 잊지말자: 이분 탐색은 정렬 후 사용

풀이

# middle 값 찾고
# N개의 나무에서 뺀값을 더해서 (음수면 포함)
# M과 비교 후 맞으면 출력
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort()
# print(trees)

left = 1
right = trees[-1]

while left<=right:
    mid = (left+right)//2
    sum = 0
    # print('mid:',mid)
    for tree in trees:
        if tree >= mid:
            sum += (tree-mid)
    if sum >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)