[백준] 2805번 나무 자르기

문제 내용

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

풀이 과정

-이분탐색으로 판단하고 문제풀이를 진행함.

풀이중 문제점

1.이분탐색 종료지점에 대한 불확실함.

 

문제점 해결 과정

1.start값의 변경을 통해 반복문을 탈출하였음.

 

해결 코드

import sys
 
sys_input=sys.stdin.readline
 
n,m=map(int,sys_input().rstrip().split())
trees=sorted(list(map(int,sys_input().rstrip().split()))) #정렬까지 시킴
 
end=trees[-1] #가장 큰값을 끝으로 잡음 or 정렬 안시킬거면 max(trees)해도됨
start=1
 
while start<=end:
    mid=(start+end)//2
    cur=0
    for t in trees:
        if t>mid:
            cur+=t-mid
 
    if cur>m:
        start=mid+1
    elif cur<m:
        end=mid-1
    else:
        start=start+1
 
print(end) #start로 while을 탈출하기에 end가 답이됨

주요 개념 

• 이분 탐색(Binary Search)