99클럽 코테 스터디 2일차 TIL + 랜선 자르기

오늘의 회고

이분탐색이라는 것을 처음 알게되었다.

특정 조건에 만족하는 값을 찾을 때 1부터 쭉 대입해도 작동하지만,

그만큼 연산이 많아져 값을 찾는데 오래 걸리게 된다.

최소값과 최대값을 지정해준 후 중간값을 대입해보고

찾은 값이 목표하는 값보다 크거나 같으면 중간값을 하나 증가시키고

찾은 값이 목표하는 값보다 작으면 중간값을 하나 감소시켜서

최대 목표 값이 나올때까지 반복시킨다.

def find_max_length(k, n, lengths):
    start, end = 1, max(lengths)
    result = 0

    while start <= end:
        mid = (start + end) // 2
        count = sum(length // mid for length in lengths)

        if count >= n:
            result = mid
            start = mid + 1
        else:
            end = mid - 1

    return result

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

print(find_max_length(k, n, lengths))