이분탐색 | BOJ 백준 2512번 예산 | Python


created_at : 23 April 2024 - 2 mins read time
Tags: 이분탐색

Table of Contents


BOJ 백준 2512번 예산 | Python

📌 백준 2512번 문제 바로가기

🔎 문제 설명

🩶 실버 2

- 난이도 ★☆☆☆
- 이분탐색

이분탐색의 대표적인 예시 문제이다. ‘백준 나무 자르기 문제’ 와 상황이 거의 비슷한 문제라 이 문제를 접했다면 어렵지 않게 해결할 수 있다.


📌 문제 풀이 큰 틀은 다음과 같다.

  • 기준점(mid) = 가능한 한 최대의 총 예산
  • 정해진 총액 이하에서 기준점을 기준으로 합을 계산



💻 내 코드

import sys
input = sys.stdin.readline

N = int(input())
cities = list(map(int, input().split()))
budget = int(input())


start, end = 0, max(cities)
answer = 0
total = 0

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

    for i in cities:
        if mid > i:
            total += i
        else:
            total += mid

    if total > budget:
        end = mid - 1
    else:
        start = mid + 1
        answer = mid

print(answer)




 

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).