[Baekjoon Online Judge] 백준 2512번 예산(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2512번 예산

(Python)

(글쓴날 : 2020.04.06)

 

---

* Baekjoon Online Judge, 백준 2512번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2512번 예산

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2512

2512번: 예산

---

2) 풀이 과정

각 지방들이 요청한 예산들과 국가예산의 총액이 주어지고, 상한액을 정하여 지방에 배정한 예산들의 합이 국가예산의 총액을 넘지 않도록 했을 때 배정한 예산들 중 최댓값을 출력하는 문제입니다.

만약, 상한액 이하의 예산이 요청되면, 요청한 금액을 그대로 배정하고, 상한액 이상의 예산이 요청될 경우 상한액 만큼만 배정됩니다.

따라서, 상한액이 배정한 예산들 중 최댓값이 됩니다.

 

저의 경우, 이분 탐색의 파라메트릭 서치를 적용하여 문제에 접근했습니다.

상한액의 범위를 좁혀 나가며 탐색을 하다가, 총액 보다 배정한 예산들의 합이 작을 경우 그때의 상한액을 저장해두었고, 탐색이 끝났을 때 저장되어 있던 상한액을 출력해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
inquiredBudget = list(map(int, input().split()))
totalBudget = int(input())
result = 0
left = 0
right = max(inquiredBudget)
 
while left <= right:
    assignedBudget = 0
    mid = (left + right) // 2
 
    for budget in inquiredBudget:
        if budget - mid < 0:
            assignedBudget += budget
            continue
        assignedBudget += mid
    
    if totalBudget < assignedBudget:
        right = mid - 1
    else:
        result = mid
        left = mid + 1
 
print(result)

---