[python] 백준 16564번 - 히오스 프로게이머

N개의 캐릭터와 각 캐릭터는 X의 레벨을 가진다.

레벨을 최대 총합 K만큼 올릴 수 있을 때, 최대 팀 목표레벨 T(min(X))를 구하는 문제.

 

그냥 이분 탐색 문제이다.

 

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
X = [0] * N
for i in range(N):
    X[i] = int(input())

start = min(X)
end = min(X) + K

while start <= end:
    mid = (start + end) // 2
    total = 0
    for x in X:
        if mid > x:
            total += mid - x
    if total <= K:
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

찾고자 하는 값을 T로 두었다.

start는 당연히 min(X)라고 생각했지만, end는 처음에 max(X) + K인 줄 알았다.

하지만 다시 생각해보니 min(X) + K여도 된다는 사실을 알았다.

 

이분 탐색 공부는 여기서 끝낼 것 같다.