[파이썬/Python] 백준 2512번: 예산

숨·2024년 8월 14일

📌 문제 탐색하기

N : 지방의 수 $(3 ≤ N ≤ 10,000)$
N개의 정수 : 각 지방 예산 요청 $(1 ≤ 정수 ≤ 100,000)$
M : 총 예산 $(N ≤ M ≤ 1,000,000,000)$

정해진 총액 내에서 배정 가능한 예산 중 최댓값을 구하는 문제이다.

문제 풀이

⭐️ 예산 배정하는 법

모든 요청 배정 👌 → 요청 금액 그대로 배정

모든 요청 배정 🚫 → 정수 상한액을 그 이상의 예산 요청에 배정

위의 방법에 따라 예산의 상한액은 다음과 같이 결정될 수 있다.
1️⃣ 시작 금액 0 ~ 예산 금액 중 최대 금액의 사이
2️⃣ 각 예산과 상한액 중 더 작은 금액들을 합한 값 < 총 예산

0부터 최대 예산 요청 금액 사이의 금액들을 탐색하면서 적절한 상한액을 찾는다.
합한 값들이 총 예산보다 크다면 상한액을 더 작은 범위에서 찾아보아야 하고,
만약 저 조건을 성립한다면 해당 값을 상한액으로 결정하고 더 큰 값을 살펴본다.

이를 이분탐색을 통해 찾아본다.

가능한 시간복잡도

while문으로 0부터 max(예산) 사이에서 이분탐색 → $O(log(max(예산)))$
현재 상황에서의 총 예산 합 계산 → $O(N)$

최종 시간복잡도
총 $O(N * log(max(예산)))$ 이 된다.
최악의 경우 $O(10^4 * log(10^9))$ 이 되는데
이는 1초 내에 연산이 가능하다.

알고리즘 선택

0부터 최대 예산 요청 금액 사이의 금액들을 확인하면서 적절한 예산 상한액을 이분 탐색으로 찾아낸다.

이분 탐색 구현

1️⃣ 시작값을 0, 마지막값을 예산들 중 최댓값으로 지정하고 중앙값을 현재 예산 상한액으로 정의한다.
2️⃣ 현재 예산 총액을 0으로 초기화한다.
3️⃣ 시작값이 마지막값과 같아지거나 더 작아질 때까지 탐색을 지속한다.
4️⃣ 현재 상한액일 때 지불되는 전체 예산 합을 계산한다.
5️⃣ 합 > M (예산 총액)라면? → 마지막값을 mid-1로 변경한다.
6️⃣ 합 < M (예산 총액)라면? → 현재 값을 상한액으로 갱신하고 시작값을 mid+1로 변경한다.
7️⃣ 이분 탐색이 종료될 때까지 탐색을 지속한다.

📌 코드 설계하기

N 입력
예산 입력
M 입력
이분탐색
결과 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. 지방의 수 N을 입력받는다.
N = int(input())

# 2. 각 지방의 예산들을 리스트로 입력받는다.
budgets = list(map(int, input().split()))

# 3. 총 예산 M을 입력받는다.
M = int(input())

# 4. while문을 통해 이분탐색을 진행한다.
start = 0
end = max(budgets)
answer = 0

while start <= end:
    mid = (start + end) // 2
    total_budgets = 0

    for budget in budgets:
        total_budgets += min(budget, mid)

    if total_budgets > M:
        end = mid - 1
    else:
        answer = mid
        start = mid + 1


# 5. 예산 총액을 출력한다.
print(answer)