백준[ 16564 | Python ] 히오스 프로게이머

문제

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

풀이

N과 K의 범위(1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000)가 넓은 범위로 min()과 list.index()를 이용한다면 시간복잡도가 보장되지 않아 시간초과가 뜨게된다.

따라서 이진탐색을 이용하게 되는데 이를 위해 탐색할 범위 값 l,r을 정의해준다.
하지만 이진탐색을 그대로 이용하기 위해서는 정렬된 리스트가 필요하기 때문에 원하는 값을 낼 수 없다.

이를 위해 리스트에 있는 값을 그대로 이용하지 않고 캐릭터의 레벨이 최대인 경우의 값 m을 탐색범위로 잡아준다.

l은리스트안에서의 최소 값 r은 리스트 안에서의 최대값과 레벨을 올릴 수 있는 값 K를 더한 값으로 설정한다.

함수 calc는 레벨이 m을 넘지않는 캐릭터의 레벨을 m으로 만들기 위해 필요한 레벨의 값을 반환한다.
이를 이용해 현재 m(최대 레벨)을 넘지 않는 캐릭터가 m이 되기 위해 필요한 값 을 올릴 수 있는 레벨의 값인 K와 비교해 K보다 높다면 r을 현재 목표로 삼은 값 m보다 1 낮은 값으로, 낮다면 l을 현재 목표로 삼은 값 m보다 1 높은 값으로 설정해주며 이를 res 변수에 저장한다.

이 범위를 모두 탐색하면 원하는 값을 반환한다.

import sys
input = sys.stdin.readline

N,K = map(int,(input().split()))
X = sorted([int(input().rstrip()) for _ in range(N)])

l, r = min(X), max(X)+K

def calc(lst, m):
    t = 0
    for num in lst:
        if num >= m:
            break
        t += m-num
    return t

while l <= r:
    m = (l+r)//2
    if calc(X,m) <= K:
        res = m
        l = m+1
        
    else:
        r = m-1

print(res)

생각 & 정리

이진 탐색을 통해 가장 적은 캐릭터에 1을 더해가며 해결을 하려고 했는데, 시간복잡도가 보장되지 않았다. 오랜만에 푸는 이진탐색 문제에 탐색할 값의 범위 설정과 이를 어떻게 활용할지 고민하다가 다른 풀이를 참고했는데, 그 코드를 봐도 왜 코드를 이렇게 작성했는지 잘 이해가 되지 않아 하나하나 뜯어보는 과정에서 많은 것을 배워간다는 생각이 들었다.

풀이를 찾아보는 과정에서 크게 다르지 않은 풀이들이 올라왔는데, 이를 설명해주는 사람이 없어 답답함을 느끼는 사람이 있을까하는 마음에 설명을 덧붙여 공유하게 되었다.