[BOJ] 2512 : 예산 [이분탐색](Python)

문제 링크

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

2512번: 예산

소스 코드

import sys

def main():
    n = int(input())
    nums = sorted(list(map(int, sys.stdin.readline().strip().split())))
    m = int(input())

    low, high = 0, max(nums) # 최소, 최대

    answer = 0 # 최종 정답 저장
    while low <= high:
        total = 0
        mid = (low + high) // 2 # 중간값

        for num in nums: # 예산에 따라 추가
            total += min(num, mid)
        
        if total <= m: # 한도를 넘지 않는 경우
            low = mid + 1
            answer = mid
        else: # 한도 초과인 경우
            high = mid - 1

    print(answer)

if __name__ == '__main__':
    main()

 

해설

• 이분 탐색(binary search)

이것 역시 강의를 듣고 나서 오랜만에 복습을 하고자 이진 탐색의 기본 유형을 찾아 풀이한 것입니다.

엄청 간단한 편에 속하는 문제 유형이죠.

 

한가지 미스였던 점은 정렬입니다.

이 풀이에서는 어차피 매번 nums에 저장된 값을 다 뒤져서 total에 덧셈을 수행하므로 정렬할 필요가 없었습니다.

원래는 일정 조건을 만족하면 for문에 break를 걸어주려고 ㅎㅎ..

---

시간복잡도

이 풀이의 총 시간 복잡도는 O(NlogM)입니다.

이분 탐색을 수행하는 경우 전체 범위를 계속해서 2로 나누는 시간 복잡도를 가지게 되죠.

예를 들어 탐색 최대 범위가 M=128일 경우, 최초엔 64, 다음엔 32, 16, 8, 4, 2, 1 ..

이런 식으로 아무리 많아도 'log2의 M'번 연산을 수행하게 됩니다.

따라서 이것이 O(logM)이 됩니다.

(여기서 N이 아닌 이유는 N은 개수이고, M은 실제 예산 최댓값이라서 그렇습니다.

가장 정확한 것은 max(N)인데 보기 흉하니 logM이라고 했습니다)

 

그리고 이분 탐색을 수행할 때마다 nums에 저장된 모든 값에 대해 탐색이 수행됩니다.

즉 O(N)만큼의 시간이 걸리는 것이죠.

따라서 둘을 곱한 O(NlogM)의 시간 복잡도라고 볼 수 있겠습니다.

---

이분 탐색

우리가 구하고자 하는 예산은 최소 0원부터 최대 max(nums)입니다.

그 사이의 어떤 값을 정했을 때 총예산을 넘지 않으면서도 최대한 많은 자원을 활용할 수 있게 되는지 탐색하는 거죠.

low, high = 0, max(nums)

 

매 탐색마다 예산과 nums의 값들을 비교하여 작은 것을 추가합니다.

예를 들어 현재 예산이 127이고, 120, 110, 140, 150이 nums에 저장되어 있다고 합시다.

이때는 127을 초과하지 않는 120, 110은 그대로 사용되고, 이를 초과하는 140, 150은 값이 짤려서 127, 127만큼 사용될 것입니다.

따라서 어떤 예산이 정해지든지간에 min 함수를 사용하여 작은 값을 사용한 총예산에 더해주면 됩니다.

answer = 0 # 최종 정답 저장
while low <= high:
    total = 0
    mid = (low + high) // 2 # 중간값

    for num in nums: # 예산에 따라 추가
        total += min(num, mid)

 

그리고 이 총예산이 실제 한도를 넘는지 아닌지 비교하면 되겠죠.

총예산이 최대 한도를 초과하지 않는 경우에만 최종 정답을 업데이트하며 추가탐색을 진행합니다.

이때 논리를 조금 더 자세히 들여다보면,

 

총예산이 최대 한도를 초과하지 않는 다는 것은 = 예산을 늘려도 된다, 입니다.

아직 돈을 덜 썼으니 범위를 높여서 mid의 값을 높여야 하죠.

반대로 최대 한도를 초과하는 경우는 = 예산을 줄여야 한다, 입니다.

돈을 너무 썼으니 범위를 낮춰서 mid의 값을 줄여야 합니다.

 

이 논리에 맞게끔 low, high를 mid 중심으로 조절하여 while문을 반복하는 것입니다.

if total <= m: # 한도를 넘지 않는 경우
    low = mid + 1
    answer = mid
else: # 한도 초과인 경우
    high = mid - 1