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

백준 16564 - 히오스 프로게이머

시간 제한 2초, 메모리 제한 512MB

# 조건

• 성권이는 Heroes of the Storm 프로게이머 지망생이다.
• 이 게임에는 총 N개의 캐릭터가 있다.
• 그리고 현재 각 캐릭터의 레벨은 Xi이다.
• 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다.
• 팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가?
  • 예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다.
  • 라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있다.

입력

• 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000)
• 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1_,_ X2, X3, ... , Xn 으로 주어진다. (1 ≤ Xi ≤ 1,000,000,000)

출력

• 가능한 최대 팀 목표레벨 T를 출력한다.

# 접근 방법

• 이분 탐색을 이용하여 풀어준다.
• 평균을 가장 높게 올려야 되는 것이므로 다양한 캐릭터를 적절히 레벨을 올려주는 것이 핵심이다.
  • start는 level의 최솟값
  • end는 최솟값에 k만큼 더한 값이다.
• mid 값을 구한 뒤 모든 레벨을 순회하며 mid보다 작다면 mid와의 차이 값을 temp에 더해준다.
• temp가 K보다 작거나 같다면, result를 갱신해주고 start를 mid + 1로 변경해준다.
• 크다면, end를 mid - 1 로 변경해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, K = map(int, input().split())  
level = []  
for _ in range(N):  
    level.append(int(input()))  
level.sort()  
start = level[0]  
end = level[0] + K  
result = 0  
while start <= end:  
    mid = (start+end) // 2  
    temp = 0  
    for i in level:  
        if i <= mid:  
            temp += (mid - i)  
    if temp <= K:  
        start = mid+1  
        result = mid  
    else:  
        end = mid - 1  

print(result)