[2805] 나무 자르기

문제 이해

h로 자른 윗 부분 가져갈거고 m만큼 필요함
높이를 하나씩 잘라보면 백만 * 20억이 드니 이분탐색으로 시간 절약 필요

========================================
코드 계획

n, m 입력
map으로 입력 받아서 tree 배열에 저장
정답 answer 초기화
low = 1
high = max(tree) + 1

low <= high 동안 반복
1) mid 계산
2)h 변수 초기화
3) tree 순회하며 잘린 길이 h에 저장
4) h가 m보다 크거나 같은지 확인(문제에서 적어도라고 했으니)
가져갈 나무가 충분하다? 그러면 나무를 아껴야 하니까 low를 높여보자
정답에 h 중 큰거 저장
low = mid +1
5) 아니라면 안짤렸다. 높이를 낮추자
high = mid - 1

answer 출력

 

---

h에 다가 그냥 i를 더해서 값이 이상하게 나왔었다.

괜히 low  high 값을 잘못적은 줄 알고 바꿨는데 아무리 생각해도 맞음

그래서 print 찍어보니까 h가 너무 높았음. i-mid를 해야 하는데 그냥 i를 넣어버렸음. 

그니까 나무를 안자르고 나무를 그냥 넣어버린 것과 같은것...

 

 

import sys

input = sys.stdin.readline

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

tree = list(map(int, input().split()))

low = 1

high = max(tree)

answer = 0

while low <= high:

    mid = (low+high) // 2

    h = 0

    for i in tree:

        if i-mid > 0:

            h += i-mid

    #print(f'mid: {mid}, h : {h}')

    if h >= m :

        answer = max(answer, mid)

        low = mid + 1

    else:

        high = mid -1

print(answer)