[문제풀이]백준 2805 나무자르기

0. 당신의 개발공부에 도움이 되지 않습니다. 

 

1. 문제

문제

2. 문제 해석

 - 이분탐색으로 톱의 길이의 최댓값을 구하는 문제

 - 참고로 이분탐색을 나무 리스트에 사용하는 것이 아니라 절단기 높이를 구하는데 사용해야 한다.

 

3. 코드 

N, M = map(int, input().split()) # N: 나무 개수, M: 필요한 나무 양(길이)
N_list = list(map(int, input().split())) # N개의 나무리스트

bottom, top = 0, max(N_list) # 절단기 높이와 바닥을 설정한다.

while bottom <= top: # 이분탑색으로 구하기 위해 절단기 높이가 0이 될때 까지 돌린다.
    p = (bottom+top) // 2 # 절단기의 중간 위치를 구한다.
    count1 = 0 # 자른 나무의 양 확인용
    for tree in N_list: # 나무 리스트에서 나무를 하나씩 잘라 count한다.
        if tree >= p:
            count1 += tree - p
    if count1 >= M: # 자른 나무가 필요한 나무보다 크면
        bottom = p + 1 # 더 조금 자르기 위해 절단기를 높힌다.
    else:
        top = p - 1 # 덜 자르기 위해 절단기를 낮춘다.
    
print(top) #최종 절단기의 높이를 구한다.