[백준/Python] 16564 히오스 프로게이머

문제 링크

16564번: 히오스 프로게이머

 

문제 풀이

• 일반적인 이분 탐색 문제이다. 여기서 주의해야 할 점은 end 값 설정이다.
• 만약 캐릭터 레벨의 총합(sum(arr))보다 k가 무수히 크다면 end 값은 단순히 총합이 아닌 총합과 k를 더한 값이 되어야 한다.

 

전체 코드

import sys

n, k = map(int, sys.stdin.readline().split())
arr = [int(sys.stdin.readline().strip()) for _ in range(n)]

start = 1
end = sum(arr) + k
res = 0
while start <= end:
    mid = (start + end) // 2
    total = 0
    for x in arr:
        if x < mid:
            total += mid - x
    if total > k:
        end = mid - 1
    else:
        res = max(res, mid)
        start = mid + 1

print(res)