[백준] Python - 2512 예산

하아... 이 문제.. 금방 풀릴 것 같더니, 은근히 오래 걸렸다..ㅠㅠ 난 이분탐색 알고리즘 문제를 풀 때마다 left, right 범위를 포함하는 부분이 너무 어렵다. 풀고 나서도 찝찝한 부분이다.

 

---

 

문제 링크

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

2512번: 예산

 

문제 풀이

이 문제는 정해진 총액 내에서 가능한 한 최대의 총 예산을 결정하는 문제로써, 이분 탐색 알고리즘을 적용한다.

문제에서 상한이 주어지면 이분 탐색 알고리즘 문제인지 고려해보는 것이 좋은 것 같다.

1. 우리가 구해야하는 예산을 이분 탐색의 범위로 잡는다.
2. left가 rght 내에 있는 한, 중간값 mid를 도출하여 다음 계산의 범위로 잡는다.
   1. mid를 상한액이라고 지정하고, 도출한 결과가 budget 범위에 있는지 확인한다.
   2. 계산한 sum_budget이 total_budget 보다 크면, 더 적은 예산으로 배정해야하기 때문에 왼쪽 범위가 되는 right = mid - 1이 된다.
   3. 반대로 sum_budget이 total_budget 보다 작으면, 더 많은 예산으로 배정할 수 있기 때문에 오른쪽 범위가 되는 left = mid + 1이 된다.

이렇게 로직을 반복하면 left가 right을 넘어가는 순간이 생기고, 이 때 최댓값을 구할 수 있다.

주의할 점은 마지막 if문에서 mid(상한액)으로 잘라서 sum_budget이 total_budget보다 크면 안되기 때문에, 작거나 같은 경우를 한 조건으로 묶어줘야 한다.

 

 

예제 입력 1

4
120 110 140 150
485

 

예제 출력 1 

127

 

과정

left, mid, right, sum_budget

0 75 150 300
76 113 150 449
114 132 150 494
114 122 131 474
123 127 131 484
128 129 131 488
128 128 128 486

 

예제 입력 2

5
70 80 30 40 100
450

 

예제 출력 2

100

 

과정

left, mid, right, sum_budget

0 50 100 220
51 75 100 290
76 88 100 308
89 94 100 314
95 97 100 317
98 99 100 319
100 100 100 320

 

전체 코드

from sys import stdin

num = int(stdin.readline())
budget = list(map(int, stdin.readline().split()))
total_budget = int(stdin.readline())

def solution(num, budget, total_budget):
    result = 0
    # 배정될 예산을 이분 탐색의 범위로 잡음
    left, right = 0, max(budget)

    while left <= right : # left가 rigit보다 커진것만 아니면
        sum_budget = 0
        mid = (left + right) // 2

        for x in budget :
            sum_budget += min(mid, x)
        # print(left, mid, right, sum_budget)
        
        # 계산한 예산이 배정된 예산을 넘으면 => 더 적은 예산으로 배정해야 함
        if sum_budget > total_budget :
            right = mid - 1
        # 계산한 예산이 배정된 예산보다 적으면 => 더 많은 예산을 배정할 수 있음
        else :
            left = mid + 1
        
        result = right
        
    return result


print(solution(num, budget, total_budget))