[S3] 백준 2512 - 예산 (Python3)

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

2512번: 예산

 

---

해결방법

이분 탐색으로 풀이한다.

풀이👀

최소값과 최대값을 lo와 hi라고 하고, 그 안에서 binary search를 한다.
동작 과정은 아래와 같다.

• mid = (lo + hi) // 2 라 한다.
• ① mid를 상한액으로 지정한 뒤, 지방의 예산요청을 계산하여본다.
• 만약 합산한 게 국가예산을 넘어서면 hi = mid로 하여 다시 계산하고,
• 반대로 국가예산보다 적다면 lo = mid로 하여 다시 계산하여 ①을 다시 한다.

주의할 점은 lo = 0, hi = max(각 지방의 예산요청 리스트)+1 이다.

0부터 찾는 이유는 국가예산이 모자를 수도 있기 때문이다.

EX 1)
5
100 100 100 100 100
10

answer)
2

 

---

코드🐱‍👓

"""
최소값과 최대값을 lo와 hi라고 하고, 그 안에서 binary search를 한다.
동작 과정은 이러하다.
mid = (lo + hi) // 2 라 하고
1. mid를 상한액으로 지정한 뒤, 지방의 예산요청을 계산하여본다.
만약 합산한 게 국가예산을 넘어서면 hi = mid로 하여 다시 계산하고,
반대로 국가예산보다 적다면 lo = mid로 하여 다시 계산하여 1번을 다시 한다.
"""

input()
arr = list(map(int, input().split()))
money = int(input())
ans = -1

lo, hi = 0, max(arr) + 1
mid = (lo + hi) // 2
while lo+1 < hi:
    mid = (lo + hi) // 2  # 상한액
    need = 0
    for w in arr:
        if mid < w:
            need += mid
        else:
            need += w

    if need == money:
        ans = mid
        break
    elif need > money:  #국가예산보다 필요예산이 더 많다면
        hi = mid
    elif need < money:  #필요예산이 국가예산보다 적다면
        ans = max(ans, mid)
        lo = mid
print(ans)

코드 설명

첫 줄은 지방의 개수인데, 그냥 arr(지방 예산들 모아놓은 리스트)의 길이로 알아내도 된다. 그리고 애초에 그 변수를 쓰지 않으니 그냥 날렸다.

이 문제에서는 upper_bound를 이용해야 한다. 그래서 hi 값은 max(arr)+1이다.

---

내가 이해하기 위해 정리했던 내용

프로그램의 동작 과정을 머리로 그려보면서 어디가 잘못 되었는지 찾았다.

EX 2)
3
100 100 100
400

upper_bound)
100

None)
99

 

None의 경우일 때 lo, hi, mid는 아래의 값대로 변화한다.

# print(lo, hi, mid)

0 100 50
50 100 75
75 100 87
87 100 93
93 100 96
96 100 98
98 100 99

분명 우리가 필요한 값은 100이지만 mid = (lo+hi)//2 라는 수식에 의해서 mid는 99가 된다.

이대로 코드가 동작하면 need = 297 인 상태라서 아래의 조건을 만족한다.

조건3)
elif need < money:  #필요예산이 국가예산보다 적다면
    ans = max(ans, mid)
    lo = mid

ans = max(ans(98), mid(99)) >> ans = 99가 되고, lo = 99.

결국 while 문의 조건식 "lo(99) +1 < hi(100)" 이 False가 된다. 그렇게 ans = 99인 상태로 프로그램을 종료한다.

 

 

이런 상황을 개선해주기 위해서 hi에 1을 더해줌으로써 보정한 것이다.

그러면 위의 상황에서 lo(99) +1 < hi(100+1) 은 아직 True이고, 반복문을 한 번 더 순회할 수 있게 된다.

그럼 mid = (lo(99) + hi(101)) // 2 >> mid = 100이 된다. 그리고 다시 한 번 조건③을 만족하면서 ans = 100으로 업데이트된 다음 반복문의 조건식을 불만족하여 빠져나온 뒤 정답을 출력하고 프로그램을 종료한다.

---