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

https://www.acmicpc.net/problem/16564

 

코드

n, k = map(int, input().split())
x = [int(input()) for _ in range(n)]

s, e = 1, int(1e9)+1
ans = 0
while s <= e:
    mid = (s+e)//2
    # 목표레벨 mid로 잡으면 달성 가능한지?
    need_level = 0
    for i in range(n):
        if x[i] < mid:
            need_level += mid-x[i]
    if need_level <= k:
        s = mid+1
        ans = mid
    else:
        e = mid-1
print(ans)

 

기본적인 매개 변수 탐색 방법으로 풀 수 있다.

다만, 조심해야 할 것은 초기 s와 e 값이다. 처음에는 e의 초기값을 int(1e9)으로 두고 했더니 틀렸었다. 다시 보니 이렇게 하면 가능한 팀 최대 레벨이 1,000,000,000인 경우를 구할 수 없기 때문이었다. 

s = 1, e = 10이라고 두고 가능한 팀 최대 레벨이 10이 되는 것을 구하는 경우를 생각해보니 mid=10이 되기 전에 s=10, e=10이 되어서 while문을 빠져나오기 때문에 mid=10일 때 가능한지 여부를 알 수 없게 되어서 ans는 절대 10이 될 수 없었다.

이제까지 이분 탐색에서 탐색 범위의 경계값도 포함된다고 생각했는데, 아니었다. 앞으로는 경계값이 포함될 수 있는 경우를 고려하여 범위를 설정하도록 해야 겠다.