악곱 == 악성곱슬

이분 탐색

---

접근법

최대 길이부터 길이를 줄여보며 N개를 만족할 때까지 길이를 줄여보자 → 최대 길이기 2^31 - 1이라서 시간초과. 범위가 클 때는 이분탐색 등 로그스케일로 구현이 가능한 방법을 고려하자.

• 길이를 이분 탐색을 통해 반씩 줄여나갈 수 있다.
• 순차탐색을 하며 개수를 구한다.

위와 같이 구현하면 O(K*log(len(K))) 가 된다.

import sys

def get_sum(mid):
    answer = 0
    for length in lan:
        answer += length // mid
    return answer

def binary_search(n):
    start = 0
    end = 2**31 - 1

    answer = 0
    while start <= end:
        mid = (start + end) // 2
        count = get_sum(mid)
        # 아직 모자르다면
        if n > count:
            end = mid - 1
        else:
            start = mid + 1
            answer = mid
    return answer

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