동바리의 공부방

링크 : 2512번: 예산 (acmicpc.net)

코드 :

import sys
input = sys.stdin.readline
N = int(input())
member = list(map(int, input().split()))
total_money = int(input())
start = 0
end = max(member)

mid = 0
mid_val = 0

while (start <= end):
    mid = int((start + end) / 2)
    sum = 0
    for i in range(0, len(member)):
        sum += min(member[i], mid)

    if (sum > total_money):
        end = mid - 1
    else:
        start = mid + 1
        mid_val = max(mid_val, mid)
        #print(mid_val)

print(mid_val)

1. 상한선을 잘 선택해야 풀 수 있는 문제였습니다.
2. 상한선 선택은 이진탐색으로 진행합니다.
3. 상한선을 선택했다면 min 함수를 이용해 지방에게 줄 돈을 선정합니다.
4. 만일 상한선보다 작은 요청금액이라면 요청금액대로 줄 것이고, 상한선보다 큰 요청금액이라면 상한선만큼 줍니다. 이 때 내어준 총 금액은 sum 변수에 저장합니다.
5. sum 변수가 줄 수 있는 금액보다 크다면 배제합니다.
6. sum 변수가 줄 수 있는 금액보다 크거나 작다면 해당 상한선을 저장하고, 이 상한선보다 더 큰 상한선이 있는지 mid를 조정하며 찾습니다.