[#2805] 나무 자르기

문제

#2805 나무 자르기
Silver2
적용 알고리즘: 이분 탐색 알고리즘

---

풀이 방법

• 1과 나무의 최대 높이를 low, high로 잡고 이분탐색을 진행한다.
• low와 high가 교차할 때까지 이분탐색을 진행하고, high가 정답이 된다.(<- 정리가 필요한 부분…)

코드 흐름

1. 사용자에게서 입력을 받는다.
2. 입력받은 나무를 오름차순으로 정렬한다.
3. 나무의 길이 1을 low로 잡고, high를 가장 높이가 높은 나무의 길이로 잡는다.
4. mid 높이로 잘랐을 때의 나무의 합에 대해서 이분탐색을 진행한다. 이때 높이가 현재 설정 높이보다 큰 나무에 대해서 합하는 것에 대해 유의한다.(키가 작은 나무는 자를 수가 없다.)
5. 탐색해야 하는 나무의 높이를 1/2로 줄여가며 low와 high가 교차할 때까지이분탐색을 진행한다.

코드

n, m = map(int, input().split())
tree = [int(i) for i in input().split()]

tree.sort()

low = 1
high = tree[-1]
mid = 0

while(low <= high):
    mid = (low + high) // 2
    temp = 0
    for i in range(len(tree)):
        if (tree[i] - mid > 0):
            temp += tree[i] - mid
    if (temp < m):
        high = mid - 1
    else:
        low = mid + 1

print(high)

체감 난이도: 4.4/5
처음에 이 문제에 이분탐색을 적용할 아이디어가 떠오르지 않아서 참고를 했다. 이분탐색 문제는 종료조건을 파악하고, 조건문에 등호를 넣느냐, 안넣느냐도 문제 풀이에 큰 부분을 차지하는 것 같다. 마무리에 mid가 아닌 high가 출력되는 과정은 조금 더 공부가 필요할 것 같다.