백준 2805 나무 자르기 Python3

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

2805번: 나무 자르기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2805.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def find_height(left, right, trees, M):
    answer = 0
    while left <= right:
        mid = (left+right)//2
        total = 0
        for t in trees:
            if t > mid:
                total += (t-mid)
        if total >= M:
            answer = max(answer, mid)
            left = mid + 1
        else:
            right = mid - 1
    return answer

input = sys.stdin.readline
N, M = map(int, input().split())
trees = list(map(int, input().split()))
left = 0
right = max(trees)
print(find_height(left, right, trees, M))

---

풀이 과정

풀이 시간 48분

나무 M미터를 얻기 위해 목재절단기의 높이 H를 얼만큼 지정해야 할지를 구하는 문제이다.

이때, 필요한 M미터 만큼만 나무를 얻을 수 있도록 H를 최대한으로 지정해야 한다.

따라서 적절한 H값을 얻기 위해 이분탐색 알고리즘을 적용할 수 있다.

import sys
def find_height(left, right, trees, M):
	#모든 나무를 베어야 필요한 M만큼을 얻을 수 있는 경우가 있을 수 있으므로 H = 0으로 초기화
    answer = 0
    
    #이분 탐색
    while left <= right:
    	#H를 mid 값으로 가정
        mid = (left+right)//2
        #mid값으로 나무를 베었을 때 얻는 나무의 총 길이
        total = 0
        for t in trees:
            if t > mid:
                total += (t-mid)
        
        #total이 M보다 크거나 같은 경우,
        if total >= M:
        	#해당 mid값을 H로 설정 가능하므로 answer값을 갱신
            answer = max(answer, mid)
            #가능한 최대 높이를 찾기 위해 left 범위를 늘린다
            left = mid + 1
        
        #total이 M보다 작은 경우,
        else:
        	#해당 mid값으로 필요한 M만큼의 나무를 얻지 못하므로, right 범위를 줄인다
            right = mid - 1
    return answer

input = sys.stdin.readline
N, M = map(int, input().split())
trees = list(map(int, input().split()))

#H의 최솟값은 0이 될 수 있으므로 0으로 left값을 초기화
left = 0
#H의 최댓값은 M = 1인 경우를 생각할 수 있다
#나무 중 최대 높이인 나무의 높이로 지정하면 나무를 0만큼 얻게 되므로 이 경우를 최대로 설정하였다
right = max(trees)
print(find_height(left, right, trees, M))

#시간복잡도 = O(log n), 공간복잡도 = O(n)