[이분탐색/백준] 2805번 : 나무 자르기

- 문제 : www.acmicpc.net/problem/2805

 

Silver Lv2 문제다. 전에 풀었던 이분탐색과 비슷해서 비슷한 풀이로 풀어봤는데 47%에서 계속 ValueError가 발생했다.

그래서 블로그 풀이 보고 해결했다. 

 

 

- 정답 풀이1: 

참고한 포스트

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

right=max(h)
left =1

while(left <= right):
    mid = (left + right) // 2
    get_trees = 0
    for i in h:
        if(i > mid):
            get_trees += (i - mid)
    if(get_trees >= m):
        left = mid + 1
    else:
        right = mid - 1

print(right)

 

- 정답 풀이 2:

나름 디버깅해봤는데 answer에 아무것도 없는 경우가 있는 것 같다. 

그래서 마지막에 answer의 원소가 있는 경우와 없는 경우를 나눠서 출력하니 정답이 떴다.

추가로 이때 left = 1로 시작해야 중간에 안 틀린다. 

n, m = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort()

answer = []
left, right = 1, trees[-1]
while left <= right:
    mid = (left + right + 1) // 2
    
    result = 0
    for tree in trees:
        if tree > mid:
            result += tree - mid
    
    if result >= m :
        left = mid + 1
        answer.append(mid)
    else:
        right = mid - 1

if len(answer) == 0:
    print(0)
else:   
    print(max(answer))

- 시도했던 풀이 

n, m = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort()

answer = []
left, right = sum(trees) // m , trees[-1]
while left <= right:
    mid = (left + right) // 2
    
    result = 0
    for tree in trees:
        if tree > mid:
            result += tree - mid
    
    if result >= m :
        left = mid + 1
        answer.append(mid)
    else:
        right = mid - 1
    
print(max(answer))