[백준 2512 / Python / 실버2] 예산

문제

 

주어진 예산 안에서 요청받은 금액을 배정해 주어야 한다.

예산이 충분하다면 요청받은 대로 전부 다 주면 되지만, 예산이 부족하다면 상한가를 정해서 최대한 많은 예산을 배분해야 한다.

즉 상한가를 정하고, 모든 예산을 전부 소모한다면 최적의 해다.

 

import sys

input = sys.stdin.readline

"""

1. 모든 요청을 줄 수 있다면 다 준다

2. 상한액을 정해서, 상한액 이상인 요청엔 상한액만 준다. 상한액 이하의 요청은 그대로 준다

"""

N = int(input())

reqs = list(map(int, input().split()))

budget = int(input())

def calc(limit, arr):

    """

    상한가를 고려해, 지급해야 할 금액 계산

    limit: 상한가

    """

    left = 0

    right = len(arr) - 1

    limit_idx = 0

    while left <= right:

        mid = (left + right) // 2

        if arr[mid] >= limit:

            right = mid - 1

            limit_idx = mid

       

        else:

            left = mid + 1

   

    # 상한가보다 낮은 좌측 금액 합계 (요청받은 금액 다 줌)

    left_sum = sum(arr[:limit_idx])

    # 상한가보다 높은 우측 금액 합계 (상한가 만큼만 줌)

    right_sum = limit * len(arr[limit_idx:])

    # 총 금액 리턴

    return left_sum + right_sum

if sum(reqs) <= budget:

    """예산이 충분할 경우"""

    print(max(reqs))

else:

    """예산이 부족할 경우, 상한가 기준 이분탐색"""

    reqs.sort()

    left = 1

    right = reqs[-1] - 1

    while left <= right:

        # mid는 현재 상한가

        mid = (left + right) // 2

        total = calc(mid, reqs)

        # 예산이 딱 맞는다면 바로 리턴 (최적 상한가)

        if total == budget:

            right = mid

            break

        elif total > budget:

            right = mid - 1

        else:

            left = mid + 1

   

    # 최대한 많은 예산을 써야 하므로 right 출력

    print(right)

 

우선 나는 2개의 이분탐색을 활용했다.

 

첫 번째는 "상한가"기준 이분 탐색이다. 최소 상한가는 1이고 최대 상한가는 가장 높은 요청 금액 - 1이다. -1을 하는 이유는 , 가장 높은 요청 금액이 상한가일 경우, 즉 -1을 하지 않은 경우는 예산이 충분할 경우에서 이미 필터링 되기 때문이다. 이분탐색을 진행하며 상한가를 갱신할 때마다, 해당 상한가를 적용할 경우 지급해야 하는 금액은 얼마인지 계산한다. 이것이 두번째 이분탐색 calc() 이다.

 

calc()는 상한가를 기준으로 좌측, 우측을 나누어 좌측 값들은 요청한 금액을 전부 주고, 상한가 이상인 우측 값들은 상한가 만큼만 준다. 사실 이건 calc() 함수로 안 빼고 그냥,

for req in reqs:
    if mid < req:
        total += mid
    else:
        total += req

이렇게 반복문 해도 되긴 하다. 근데 좀 비효율적이다. 왜냐하면 모든 요소(N개)에 if 조건문을 전부 적용하며 일일이 더하기 때문이다. 그래서 조금 더 효율적인 total 계산을 위해, 이분탐색을 활용한 calc() 함수를 따로 만들었다.

 

두 방식은 생각보다 성능 차이가 많이 났다. 시간복잡도는 같은 O(NlogN) 인데도, calc() 함수의 유무에 따라 발생하는 total 계산식에서 성능 차이가 발생하는 것 같다.

 

성능 차이

 

스티커로 표기된 제출의 시간은 68ms 인데, 이게 단순 반복문으로 total을 구한 코드이다. 기존 코드가 36ms인걸 감안하면 꽤 차이가 많이 난다. 근데 결국 큰 틀에서는 같은 O(NlogN) 이기 때문에 간결하고 가독성 좋은 코드가 더 낫나 싶기도 하지만, calc() 함수로 로직을 추상화했으니 그 차이도 없는 것 같기도 하다.

 

더 추가해 보자면, calc() 함수가 호출될 때마다 left_sum을 구하기 위해 sum()을 사용해서 O(N)시간이 사용되는데, 이것도 누적 합 테이블 미리 한번 구해놓으면 상수 시간으로 최적화할 수 있긴 한데 이 문제에서는 굳이인것 같다.