[Python] 2805번 나무 자르기

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

2805번: 나무 자르기

---

22/08/28

 

보자마자 날먹 문제라고 생각했다.

 

이 문제는 그제 풀었던 1654번 랜선 자르기 문제와 거의 동일한 문제였기 때문이다.

 

단지 약간의 조건만 달랐다.

 

---

 

문제 접근 방법:

 

 

랜선 자르기 문제와 동일한데, 나무를 일정 간격으로 계속 자르는 게 아니라, 일정 높이를 두고 일정 높이 이상인 나무만 한 번 자른다는 점만 다르다.

 

다시 말해, 나누기를 하는게 아니라 빼기를 하는거다.

 

랜선 자르기 문제에 대한 해설은 아래에 있으니 참고하면 될 것 같다.

---

https://lighter.tistory.com/9

[Python] 1654번 랜선 자르기

---

코드 또한 약간의 수정만 가했다. python3로 제출한 코드이다. 더보기를 누르면 확인할 수 있다.

# 2805번 나무 자르기
# 이분 탐색, 매개 변수 탐색
'''
접근 방법:
랜선 자르기 문제와 거의 동일함.
'''
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
trees = list(map(int, input().rstrip().split()))
def binary_search(low, high, N, arr):
    if low > high:
        return high
    mid = (low+high)//2
    total = 0
    for tree in arr:
        if tree - mid > 0:
            total += (tree-mid)
    if total >= N:
        return binary_search(mid+1, high, N, arr)
    else:
        return binary_search(low, mid-1, N, arr)

print(binary_search(0, max(trees), M, trees))