[백준][이분 탐색] - 2805. 나무 자르기

문제 풀이

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

tree = list(map(int,input().split()))
lt = 1
rt = max(tree)
res = 0
#자른 값과 남은 값이 큰 경우를... 이땐 남은 값이 더 큰 경우를 찾아야 하기에..lt를 증가!
 
while lt <= rt:
    mid = (lt+rt)//2
    s = 0
    for i in tree:
        if i >= mid:
            s+= i-mid
    if s >= m:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)

• 최소한의 나무만 잘라서 원하는 값을 얻어가는 문제로 이분 탐색을 사용해 풀이가 가능하다.
• 이분 탐색은 구간을 정해 구간의 범위를 좁혀가며 해당 조건을 만족하는 값을 돌려주면 된다.
• 초기값 설정은 1 ~ 주어진 값의 최댓값을 사용하는 것이 일반적이므로 이 문제도 lt = 1 ~ rt = 주어진 값의 최대 값으로 설정했다.
• 문제를 풀때 주의해야 하는 점은 s값을 더해주는 과정인데 이는 해당 mid 값보다 작은 값은 벌목하지 않는다는 의미로 사용하면 안 되기때문에 if문으로 확인을 해주어야 했다.
• 이때 벌목해야 하는 나무는 필요한 만큼 최소화해야 하기 때문에 s가 위의 조건을 만족한다해도 더 큰 값들을 살펴보며 진행해야 한다.