[문제풀이]백준_16564_히오스 프로게이머(이분탐색)

1. 이분탐색이 복잡도가 적어 공부를 많이 해야 겠다. 

 

2. 문제

문제

3. 문제 해석

 key

  - 결론적으론 주어진 K(올릴 수 있는 총 레벨)로 캐릭들에게 최대한 균등히 분배하여 최소값을 구하는 문제이다. 

  - 이분탐색을 가장 낮은 렙에서 k이 까지로 끝과 끝을 잡고 이분탐색을 하여 pivot과 렙의 차를 합산하여 산출하면 된다. 

 

4. 코드 

import sys
input = sys.stdin.readline

# 1. n, k값을 받는다. 
n, k = map(int, input().split())
# 2. 캐릭 렙을 받는다.
n_list = [int(input()) for _ in range(n)]

# 3. 리스트에서 가장 작은 값을 bottom으로 사용 
bottom = min(n_list)
# 4. bottom 기준으로 +k 를 top으로 가져간다.
top = bottom + k
# 5. 결과값을 받을 변수
result = 0
while bottom <= top: # 6. 양 끝이 만날때 까지 반복
    pivot = (bottom + top) // 2 # 7. pivot 설정
    sum = 0 # 8. result에 담기 전 일회성 합산 변수
    for i in n_list:
        if i < pivot: # 9. 렙이 pivot보다 작으면 pivot에서 렙을 뺀 값을 저장해 둔다.(탑 개수만큼 반복)
            sum += (pivot - i)
        
    if sum <= k: # 10. 합산 한 값을 비교(합산값이 레벨 총 합보다 작거나 같으면)
        bottom = pivot + 1 # 11. 피벗 +1 한다음 바텀으로 재 지정
        result = max(pivot, result) # 12. 반복문 돌면서 계속 저장하고 끝났을때 최대값 출력
    elif sum > k:
        top = pivot - 1

print(result)