TIL-18
20210619 알고리즘 문제 풀이
백준 2805번 나무 자르기
https://www.acmicpc.net/problem/2805
N,M = map(int,input().split())
tree = list(map(int,input().split()))
def treeSum(height):
Sum = 0
for i in tree:
if i-height >0:
Sum += (i-height)
return Sum
def binarySearch(target):
start,end=0, max(tree)
ans = 0
while(start<=end):
mid = (start+end)//2
Sum = treeSum(mid)
if Sum < target :
end = mid -1
if Sum >= target:
ans = mid
start = mid + 1
return ans
print(binarySearch(M))
풀이
- 톱날의 높이가 낮을수록 더 많은 나무를 벨 수 있다
- 이진탐색 이용
- 톱날의 높이가 결정되었을 때, M미터보다 크거나 같으면, 톱날의 높이 H를 높여준다
(같을 때 톱날의 높이를 높여줘야함)- M미터보다 작으면 톱날의 높이 H를 낮춰준다
- 나무의 높이가 톱날의 높이보다 높은 경우에만 나무를 가져갈 수 있다
- 따라서 그런 경우에, sum += 나무 높이 - 톱의 높이 = tree[i] - height로 계산한다
- 결과를 return
Author And Source
이 문제에 관하여(TIL-18), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@happyeveryone96/TIL-18저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)