[Python - Binary Search] 2512 예산

📌 문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다. 

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

📌 입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. 

📌 출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다. 

📌 문제 풀이

👨‍🏫 접근

정석적인 이진탐색 문제. 어떠한 기준을 통해서 값을 찾아내야 할 때 이진탐색 알고리즘을 사용한다. 그냥 정렬된 리스트에서 이진탐색을 통해 특정 값을 찾아내기도 하지만, 이진탐색의 기조가 반씩 찾아보는 것이기 때문에, 어떠한 배열에서 조건을 만족시키는 값을 찾기 위해서도 이진 탐색을 사용한다

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline

n = int(input())
provinces = list(map(int, input().split()))
m = int(input())

pl, pr = 1, max(provinces)
ans = 0

while pl <= pr:
    mid = (pl + pr) // 2
    temp = 0
    for province in provinces:
        if mid > province:
            temp += province
        else:
            temp += mid

    if temp <= m:
        pl = mid + 1
        ans = mid
    else:
        pr = mid - 1

print(ans)

📄 준비

import sys
input = sys.stdin.readline

n = int(input())
provinces = list(map(int, input().split()))
m = int(input())

pl, pr = 1, max(provinces)
ans = 0

예산인 m이 1 이상이라서 pl을 1로 해줘도 상관 없다. pl이 1이고 pr이 1인 최소의 상황에서 (pl + pr) // 2를 하면 1이기 때문에 문제의 조건을 충족하기 때문이다.

📄 풀이

while pl <= pr:
    mid = (pl + pr) // 2
    temp = 0
    for province in provinces:
        if mid > province:
            temp += province
        else:
            temp += mid

    if temp <= m:
        pl = mid + 1
        ans = mid
    else:
        pr = mid - 1

print(ans)

탐색의 중간 지점을 검사해서 예산안의 상한선을 테스트해본다. 그렇게해서 예산을 책정했을 때, 목표 예산안을 맞추거나 넘지 않을 경우에 ans(답)에 값을 저장한다. 값을 저장하는 기준은 조건을 만족할 때이다. 이 문제를 예로 들면, 예산안은 목표치보다 적게만 잡으면 정답이기 때문에 temp(모의 예산안)이 m(목표 예산안)보다 적기만 하면 일단 조건을 만족시키는 것이다. 그렇기 때문에 ans에 답을 넣어준다.

 

먼저 모의 예산안이 목표보다 같거나 작을 경우 더 많은 예산안을 받기 위해서 pl의 값을 키운다. 그렇게 하면 모의 예산안이 (pl + pr) // 2를 통해서 더욱 커진다.

 

반대의 경우도 같은 이유다.

📌 총평

이진탐색은 누가 먼저 생각해냈을까 참으로 똑똑하다.