백준 이분탐색 문제입니다.
문제
https://www.acmicpc.net/problem/2805
이분 탐색 문제입니다. 주어진 나무(높이)들을 임의의 높이로 모두 자르고 합하여 입력받은 M보다 크거나 같을 수 있는 최대 높이를 구하는 문제입니다.
최초 해결할 시에,
나무를 자를 수 있는 모든 경우의 수 [0,1,...가장 큰 나무 높이] 리스트를 구현하고 이를 이분탐색하며 조건에 맞는 최대 높이를 구하는 방식으로 풀었습니다.🐱🐱🐱
[나의 풀이1]
(메모리 초과)
def upper_bound(heights,M,trees):
start,end = 0, len(heights)
over = 0
while start<end:
mid = (start+end)//2
woods = 0
for tree in trees:
wood = tree - heights[mid]
if wood > 0:
woods += wood
if woods==M:
print(heights[mid])
exit()
elif woods<M:
end = mid
else:
if over < heights[mid]:
over = heights[mid]
start = mid+1
return heights[mid],over
N, M = map(int,input().split())
trees = list(map(int,input().split()))
trees = sorted(trees)
heights = [i for i in range(0,trees[-1]+1)]
print(heights)
heights, over = upper_bound(heights,M,trees)
print(over)
위 코드대로 라면 답은 잘나오지만 문제에서 주어진 나무의 최대 높이는 1,000,000,000이기 때문에 최악의 경우 메모리가 초과하는 오류가 발생하였습니다.🐳🐳🐳
그리하여 아래와 같이 자를 수 있는 최소,최대 높이 리스트를 없애고 이분 탐색할 때의 start=0, end='나무 최대 높이'로 지정하여 이전 방식에 비해 메모리를 적게 사용하는 방법으로 해결하였습니다.
[나의 풀이2]
def upper_bound(M,trees):
start,end = 0, trees[-1]
while start<end:
mid = (start+end)//2
woods = 0
for tree in trees:
wood = tree - mid
if wood > 0:
woods += wood
if woods==M:
return mid
elif woods<=M:
end = mid
else:
start = mid+1
return start-1
N, M = map(int,input().split())
trees = list(map(int,input().split()))
trees = sorted(trees)
# print(trees)
# heights = [i for i in range(0,trees[-1]+1)]
# print(heights)
height = upper_bound(M,trees)
print(height)
이번 문제는 다른 사람들의 풀이도 대부분 비슷한 방식이었습니다.
감사합니다.🍋🍋🍋