악곱 == 악성곱슬

이진 탐색

---

해당 문제를 처음에 딱 보면 그냥 완전 탐색을 하며 연산을 하면 될 것으로 보인다. 그리고 입력의 크기를 보면 개수가 100만이다. 그리고 수의 최대 크기는 10억이다. 여기서 순차탐색을 하며 계산을 한다면 10억 * 100만이 될 것이다. 따라서 시간 초과가 발생할 것이다.

그래서 생각해 낼 수 있는 것이 10억에 대한 값을 순차탐색이 아닌 이진탐색으로 범위를 좁혀나가는 것이다.

위의 과정으로 이진 탐색 문제라는 것을 도출해 낼 수 있다. 반복문을 사용하여 이진탐색을 구현했고, 코드는 아래와 같다.

import sys

def get_level(mid):
    result = 0
    for x in X:
        if x > mid:
            continue
        result += mid - x
    return result

def solution(x, k):
    start = 0
    end = max(x)

    answer = 0
    while start <= end:
        mid = (start + end) // 2
        total_level = get_level(mid)
        if total_level == k:
            answer = mid
            break
        if total_level < k:
            start = mid + 1
            answer = mid
        else:
            end = mid - 1
    return answer

if __name__ == "__main__":
    N, K = map(int, sys.stdin.readline().rstrip().split())
    X = list()
    for _ in range(N):
        X.append(int(sys.stdin.readline().rstrip()))
    print(solution(X, K))