[백준/Python] 2805번: 나무 자르기

문제

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

2805번: 나무 자르기

---

문제 요약

상근이는 N 그루의 나무를 절단기로 높이를 지정하고 잘라 M미터의 나무를 구하려고 한다.

 

예를 들어 한 줄에 연속해 있는 나무의 높이가 20, 15, 10, 17이라고 할 때, 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고 상근이는 길이가 5인 나무와 2인 나무를 구할 수 있다.

 

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

---

코드

# 절단기에 설정할 수 있는 높이의 최댓값을 구하는 함수
def binSearch():
    res = 0 # 절단 기에 설정할 수 있는 높이의 최댓값

    # 높이는 0 ~ 1000000000까지 가능하므로 이 값들 중 res를 이진 탐색을 통해 찾는다.
    start = 0
    end = 100000000000
    while start <= end:
        mid = (start + end) // 2
        # print(mid)

        cnt = 0 # mid로 높이를 설정했을 때 상근이가 구할 수 있는 나무 길이
        for num in arr:
            if num > mid:
                cnt += (num - mid)

        if cnt >= m: # 구한 나무 길이가 M보다 크거나 같으면 
            start = mid + 1 # 더 높은 높이에서 자를 수 있는지 탐색
            res = max(res, mid) # res 갱신

        else: # 구한 나무길이가 M보다 작다면
            end = mid - 1 # 더 작은 높이에서 자를 수 있는지 탐색

    return res


n, m = map(int, input().split()) # n: 나무의 수, m: 나무의 길이

arr = sorted(list(map(int, input().split())))

print(binSearch())

---

코드 설명

1. 한 줄에 연속해 있는 나무의 높이를 입력 받고 오름차순으로 정렬한다.

 

2. 이진 탐색을 통해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 함수 binSearch를 구현한다.

+ 가능한 높이인 0 ~ 1000000000의 값 중 조건에 만족하는 값 중 최댓값을 구한다.

 

3. binSearch의 반환 값을 출력한다.