1️⃣ 서론
백준 문제 2512번 예산 문제이며 파이썬(Python)으로 해결하였다.
2️⃣ 문제 설명
지방의 수 N이 주어지고
각 지방의 예산을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다.
마지막 줄엔 총 예산을 나타내는 정수 M이 주어진다.
이 값들은 모두 1 이상 100,000 이하이며 M과 N은 1이상 1,000,000,000 이하이다.
가능한 한 최대의 예산을 배정하는 것이 문제이다.
3️⃣ 풀이
가장 큰 예산을 찾는 문제이므로 바로 이분 탐색의 아이디어를 얻을 수 있었다.
최소의 예산을 0으로 잡고 최대의 예산을 가장 예산 요청이 큰 국가로 잡도록하자.
이렇게 이분탐색을 left <= right 까지 돌리면 가장 큰 예산을 배정할 수 있다.
4️⃣ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n = int(input())
arr = list(map(int, input().split()))
maxNum = int(input())
left = 0
right = max(arr)
while left <= right:
mid = (left + right) // 2
tmp = 0
for x in arr:
if mid >= x:
tmp += x
else:
tmp += mid
if tmp <= maxNum:
left = mid + 1
else:
right = mid - 1
print(right)
5️⃣ 마치며
실버 3문제 이니 만큼 그렇게 어려운 문제는 아니었던 듯하다.
기본적인 이분탐색 문제였는데 right를 배정된 예산들 중 최댓값을 나타내는 것이므로 right = max(arr) 이 부분이 키포인트가 아니었나 싶다.
