백준 이분탐색 문제입니다.

문제

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)

이번 문제는 다른 사람들의 풀이도 대부분 비슷한 방식이었습니다.

감사합니다.🍋🍋🍋