[BOJ] 백준 2512 예산 / 이분탐색

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

 

국가예산이 주어지고, N개의 지방에서 예산 요청이 주어질 때 정해진 예산 내에서 최대 얼마까지 배정할 수 있는 지 계산하는 문제이다.

내용은 다르지만 큰 틀은 이전에 풀었던 이분탐색 문제들과 다를 바가 없다.

 

최소 예산인 1부터 최대 예산인 max(지방의 예산요청들) 사이에서 이분탐색을 하며 그 값을 찾아내면 된다.

 

 

 

구현 언어: Python

 

import sys

r = sys.stdin.readline

def binary_search(requests: list, budget: int) -> int:
    result = 0
    left = 1
    right = max(requests)
    while left <= right:
        mid = (left + right) // 2
        total_sum = sum(mid if req >= mid else req for req in requests)
        if total_sum <= budget:
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    return result

_, bud_requests, total_bud = r(), list(map(int, r().split())), int(r())
print(binary_search(bud_requests, total_bud))

 

 

이러한 양식의 다른 문제들에서

현재 설정한 최대 상한액(mid) 기준으로 배정할 수 있는 예산액을 계산하는 total_sum 부분의 연산을 줄이기 위해서

Counter를 사용해 같은 값이 여러 개 존재하면 value*key 와 같은 방식으로 처리하곤 했다.

 

그러나 이 문제에서 예산 요청이 최대 10,000 개이다.

import sys
from collections import Counter

r = sys.stdin.readline

def binary_search(requests: Counter, budget: int) -> int:
    result = 0
    left = 1
    right = max(requests)
    while left <= right:
        mid = (left + right) // 2
        total_sum = sum(mid*cnt if req >= mid else req*cnt for req, cnt in requests.items())
        if total_sum <= budget:
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    return result

_, bud_requests, total_bud = r(), Counter(map(int, r().split())), int(r())
print(binary_search(bud_requests, total_bud))

 

위 결과를 통해 확인할 수 있는 것처럼 처리할 값의 수가 많지 않다면 오히려 Counter를 쓰는 것이 시간 효율 측면에서 떨어지는 것을 확인할 수 있었다.(위가 Counter, 아래가 일반적인 방법)

 

 

📝 데이터의 수가 많다면 Counter를 사용하는 것이 실행 시간을 줄이기 위한 좋은 시도이나,

데이터의 수가 적다면 일반적인 방법으로 계산하는 것이 오히려 좋다..!