[Python 파이썬] 백준 2512번 - 예산

2024년 7월 19일

문제 링크 : 백준 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 이하이다. 

출력

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

 

알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

---

 

문제 접근

 

상한액을 1부터 M까지 하나씩 올려보며 비교하기엔, 최대값이 1,000,000,000 이라 매우 비효율적이다. 제한 시간이 1초이기 때문에, 10억번 연산하면 시간 초과가 날 수 밖에 없다.

 

여기서 나는 상한액을 이분 탐색을 통해 찾아내면 되겠다라고 생각했다.

 

상한액으로 올 수 있는 최소값은 1, 최대값은 예산의 총 액수 이므로 다음과 같은 로직으로 이분 탐색 코드를 구성하였다.

 

순서도

1. 초기 left값은 0, right는 예산의 총 액수로 초기화한다.
또한 상한액의 최대값인 upperLimit을 선언하고, 상한액의 최소값인 1을 초기값으로 대입한다. 

2. left + right를 2로 나눈 몫을 mid로 취한다.

3. 모든 요청 예산을 순회하며 상한선이 mid일 때 요구하는 총 예산을 구한다.

4. 이 때, 요구하는 총 예산이 현재 예산 이하의 값이라면, mid와 현재 upperLimit와 비교해 더 큰 값을 upperLimit에 치환해준다.

5. 요구하는 총 예산의 값을 기준에 따라 5-1 ~ 5-3의 경우를 따른다.
5-1. 요구하는 총 예산 == 현재 예산 -> 해당 상한액이 최대값이므로 upperLimit를 return 후 종료
5-2. 요구하는 총 예산 < 현재 예산 -> 예산 총액이 남았으므로 mid를 증가시키기 위해 left에 mid + 1을 대입한다.
5-3. 요구하는 총 예산 > 현재 예산 -> 예산 총액을 넘어버렸으므로 mid를 감소시키기 위해 right에 mid를 대입한다.

6. 2 ~ 5 과정을 left가 right 이상이 될 때까지 반복한다.

 

하지만 이분 탐색을 무조건 실행하면 예외 사항이 발생한다.

다음은 문제에서 제시한 예시이다.

 

5
70 80 30 40 100
450

 

 

모든 지역에 요구하는 예산을 분배해도 현재 예산이 남는 경우이다.

이런 경우, 이분 탐색을 수행하면 449가 나오게 된다. 왜나햐면 위의 순서도에서 5-3 과정으로만 다음 반복문이 실행되기 때문.

 

그러므로 요구하는 총 예산이 현재 예산보다 작거나 같다면, 요구하는 예산들 중 최대값을 출력하고 이분 탐색은 수행하지 않도록 유도해야 한다.

 

---

입력 예제

 

4
120 110 140 150
485

 

 

 

출력 예제

 

127

 

 

---

전체 코드

 

# 2512
def binarySearch(N, requests, budget):
    # 예산은 최소 N, 최대 1,000,000,000
    left = 0
    right = budget
    # 최종적으로 출력하고자 하는 상한선 최대 값
    upperLimit = 1

    while left < right:
        # 상한선
        mid = (left + right) // 2
        nowBudget = 0
        for req in requests:
            if req <= mid:
                nowBudget += req
            else:
                nowBudget += mid

        # 현재 책정한 상한액
        if nowBudget <= budget:
            upperLimit = max(upperLimit, mid)

        # 분배했을 때, 예산 총액을 꽉 채운다면 해당 값이 최대 상한선
        if nowBudget == budget:
            return upperLimit

        # 분배했을 때, 예산 총액이 남는다면 mid를 늘려봐야 함
        elif nowBudget < budget:
            left = mid + 1

        # 분배했을 때, 예산 총액을 넘어버렸다면 mid를 줄여봐야 함
        else:
            right = mid

    return upperLimit

if __name__ == "__main__":
    N = int(input())
    requests = list(map(int, input().split()))
    budget = int(input())
    if sum(requests) <= budget:
        print(max(requests))
    else:
        print(binarySearch(N, requests, budget))

 

---

풀이 후기

 

이분 탐색 문제는 left와 right의 중간값인 mid를 어떤 값으로 지정할지, 그리고 어떤 기준에 따라 left를 치환할지 right를 치환할지 결정하는 게 가장 중요하고, 또한 가장 어려운 부분이라고 생각한다.