백준 [16564] 히오스 프로게이머(Python3)

들어가기 전에

문제를 해결하기 위해 어떤 생각을 했는지 기록하기 위해 쓰는 글입니다.

O(10^8)의 계산을 1초라 가정했습니다.

잘못되거나 개선이 필요한 부분 지적은 언제나 환영입니다!

 

지문 해석

레벨을 올릴 수 있는 총합 K를 적절히 배분해서 얻을 수 있는 가장 높은 최솟값 T를 찾아야 한다.

브루트 포스로 해결한다면 최악의 경우

O(1,000,000 * 1,000,000,000) = O(10^15) 로 시간 초과를 받는다.

이분 탐색으로 해결한다면

O(1,000,000 * log(1,000,000,000)) O(1,000,000 * 29.8) = O(29,800,000) 로 해결할 수 있다.

 

이분탐색 범위 지정

N = 2 이고 X = {10, 10}, K = 1이라면, T의 값은 어떠한 경우에도 10이 된다.

N = 1 이고 X = {10}, K = X라면, T의 최대 값은 10 + X가 된다.

따라서, 답이 될 수 있는 T의 범위는 min(X) <= T <= min(X) + (K /  N)가 된다.

 

이제 이 값을 중심으로 중간 값을 구해

이 중간 값보다 작은 Xi들이 중간 값이 되기 위해 필요한 값들의 합이

K보다 작거나 같은 경우를 확인하면 된다.

 

+++++

재채점 후 틀렸다는 결과가 나와서 뭔가 했었는데

지문에서 헷갈릴만한 점이 있었다.

처음엔 최대 팀 목표레벨 T를 구하라 한 뒤, 그 다음 줄엔 최소 T를 얻을 수 있단 식으로

T가 될 수 있는 가장 작은 값을 출력하란 걸로 착각했다.

 

기존 풀이를 보면 여기에 낚인 풀이가 좀 있다.

ex)

1 1000000000
1

answer : 1000000001

wrong : 1

 

코드

from bisect import bisect_left

N, K = map(int, input().split())
X = [int(input()) for _ in range(N)]
X.sort()
answer = 0

left, right = min(X), max(X) + K // N
while left <= right:
    mid = (left + right) // 2
    index = bisect_left(X, mid)
    total = 0
    for i in range(index):
        total += mid - X[i]
    if total <= K:
        answer = mid
        left = mid + 1
    else:
        right = mid - 1
print(answer)