[BOJ 2512][백준 2512번] 예산 (파이썬 풀이)

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

2512번: 예산

🤔 문제 설명 및 입출력

---

 

 

✍ 접근 방법

---

목표로 하는 어떠한 값이 있고, 그 값을 찾기 위해서 많은 trial && error 가 있을거 같다??? ➡ 이분탐색을 고려해봐라

 

이분탐색을 사용하기로 결정했으면, 어느 타이밍에 시작값과 끝값을 줄일지를 결정하면 된다.

 

가편성된 예산을 지방의 예산요청과 비교해보고, 가편성 예산이 크다면 원래 값을 국가예산에서 빼고, 지방예산이 크면 가편성된 예산을 국가예산에서 빼주면, 가편성 예산이 목표 예산보다 커져야할지 작아져야할지 알수 있을 거 같다.

 

 이런 논리를 코드로 바꿔보자

 

 

 

👨‍💻 소스 코드

---

• 파이썬

 

# 2512번
import sys
input = sys.stdin.readline

N = int(input())
desire_budget_lst = list(map(int, input().split()))
total_budget = int(input())

max_desire = max(desire_budget_lst)


def bin_search(start, end, total_budget):
    while start <= end:
        mid_v = (start+end) // 2
        result = do_satistfiy(mid_v, total_budget)
        # 가예산으로 전부 떡을 치면 --> 좀 더 올려보자
        if result:
            ans = mid_v
            start = mid_v + 1
        # 가예산 편성이 안되면 --> 좀 낮추자
        else:
            end = mid_v - 1
    return ans


def do_satistfiy(mid_v, total_budget):

    for budget in desire_budget_lst:
        total_budget -= mid_v if mid_v <= budget else budget

    # 가측정된 예산으로 모든 도시에 예산 할당이 가능하면 True 반환한다 --> 가측정 예산 키우자
    return True if total_budget >= 0 else False


print(bin_search(0, max_desire, total_budget))

 

 

코드 짜면서 나도 모르게 삼항연산자가 튀어나왔다...이게...골드의 힘????

🔥 강평

---

이분탐색 연습이 많이 필요하다고 생각해서 계속 이분탐색 문제를 풀고 있는데, 이제 슬슬 문제의 난이도를 높여봐도 괜찮을거 같다.