[백준] 2805-나무 자르기

 

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

2805번: 나무 자르기

문제 한줄 이해

-N의 나무가 일자로 서있을때 높이에 따라 싹뚝 잘랐을때 잘려나간 나무의 길이의 합이 적어도 M미터의 나무를 집에 가져가기 위한 높이의 최대값 구하기  

 

생각난 풀이

1번째 방법: 우선 N과 M의 범위가 생각보다 크다고 생각이 들어 이분탐색을 통해 해결해야 겠다고 생각했다.

import sys

n, m = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
tree.sort()

start = tree[0]
end = tree[-1]
ans = 0
while start<=end:
    result = 0
    mid = (start+end)//2
    for i in tree:
        if i > mid:
            result += i-mid
    if result > m:
        start = mid+1
        if ans < mid:
            ans = mid
    elif result < m:
        end = mid-1
    else:
        ans = mid
        break
print(ans)

처음에 start값과 end값을 단순히 나무들의 높이가 최소 최대값으로 설정하면 된다고 생각했다.

하지만

N = 3 M = 9

     3 4 5     

이런 경우에  높이가 0일때와 1일때 반영이 되지 않는 코드였기 때문에 

start = 0
end = tree[-1]
ans = 0

이와 같이 수정했다.