[백준] 2512 예산

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

국가 예산을 초과하지 않으면서 최대한 받을 수 있는 상한액을 구해야하므로 이분 탐색을 이용하였습니다.

이분탐색의 최솟값은 0원, 최댓값은 현재 예산 요청의 최댓값을 지정하였습니다.

2) 알고리즘

• 이분 탐색

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())                           # 예산 요청의 개수
nums = list(map(int, sys.stdin.readline().split()))     # 예산 요청 금액들
government = int(sys.stdin.readline())                  # 정부의 총 예산

answer = 0                      # 최대 상한액
low, high = 0, max(nums)        # 최솟값 0, 최댓값은 예산 요청의 최대액

while low <= high:              # 이분탐색
    mid = (low+high) // 2       # 현재 상한액

    tmp_sum = 0                 # 상한액 이하로 받게끔 하였을때, 정부에 요청하는 총 예산
    for num in nums:
        if mid <= num:          # 상한액 이상을 요청하면, 상한액만 요청 가능하도록 설정
            tmp_sum += mid
        else:                   # 상한액 이하 요청이면, 요청한 금액 그대로
            tmp_sum += num

    if tmp_sum > government:    # 정부 예산을 초과하면 상한액을 더 낮춤
        high = mid - 1
    else:                       # 정부 예산 초과 안하면 상한액을 조금 더 높임
        low = mid + 1
        answer = mid

print(answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2512

2512번: 예산

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다