[python] 백준 16564 :: 히오스 프로게이머 (이분 탐색)

[히오스 프로게이머]

# 문제
성권이는 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를 출력한다.

 

풀이

전체 코드

import sys

# 입력 받기
n, k = map(int, input().split())
levels = [int(sys.stdin.readline()) for _ in range(n)]

# 입력 받은 값 정렬
levels.sort()

# 탐색 범위 설정
left, right = levels[0], levels[-1] + k

# mid 값보다 작은 level 값들의 차이의 총합
def get_diff(mid):
    diff = 0
    for level in levels:
        if level < mid:
            diff += mid - level
        else:
            break
    return diff

# 이진 탐색 실행
while left <= right:
    mid = (left + right) // 2
    diff = get_diff(mid)
    if diff <= k:
        left = mid+1
    else:
        right = mid - 1

# 최소값 출력
print(right)

 

1. 탐색 범위 설정

• 오름차순으로 정렬한다.
• 최대값은 현재 가장 높은 레벨 + 올릴 수 있는 레벨인 k로 설정한다.
  (현재 가장 높은 레벨로 설정하면 안된다 ❌ 이미 젤 높은 레벨에도 값이 더해질 수 있으니까!!)

# 입력 받은 값 정렬
levels.sort()

# 탐색 범위 설정
left, right = levels[0], levels[-1] + k

 

2. 올려야 하는 레벨 계산

• mid가 되기 위해 올려야 하는 레벨의 총합을 구하는 함수를 만든다.
• diff를 아래의 while 문 안에서 바로 구해도 되지만,
  이렇게 따로 함수로 분리하면 가독성을 높일 수 있고,
  이유는 모르겠지만 속도가 훨씬 빠르다.. (이유가 뭔지 아는 분 제발 알려주세요 🙏)

# mid 값보다 작은 level 값들의 차이의 총합
def get_diff(mid):
    diff = 0
    for level in levels:
        if level < mid:
            diff += mid - level
        else:
            break
    return diff

 

3. 이진 탐색 ㄱㄱ

• 최대로 가능한 레벨을 출력하는 거니까
  탐색이 종료됐을 때의right를 출력한다!

# 이진 탐색 실행
while left <= right:
    mid = (left + right) // 2
    diff = get_diff(mid)
    if diff <= k:
        left = mid+1
    else:
        right = mid - 1

# 최대로 가능한 레벨 출력
print(right)