Python 1654 : 랜선 자르기 (이분탐색,BS)

문제

풀이

• 이분 탐색
• 하나씩 줄여가면서 탐색하면 시간초과가 뜬다.
• N은 1이상 1,000,000의 범위를 가지기 때문에 범위를 절반씩 줄여가면서 타겟을 찾는 O(log n)의 시간 복잡도를 가질 필요가 있다.
• start와 end로 투 포인트(left, right)를 잡고 start가 end를 넘어설 때(랜선의 길이가 최대가 될 때)까지 반복해서 중앙 값((start + end // 2) = mid)을 구해준다.
• 반복문을 빠져나올 때 end의 값은 허용 범위 내 최대 값이다.

잡담

• 시간 초과 코드

import sys

r = sys.stdin.readline

k, n = map(int, r().split())

arr = list(int(r()) for _ in range(k))

avg = sum(arr) / n
count = 0

while count < n:
    count = 0
    avg -= 1

    for num in arr:
        count += num // avg

print(int(avg))

• 처음에는 그냥 평균 값에서 1씩 감소하면서 찾았다. 당연히 시관초과
• 밑에 이분탐색 태그를 보고 start, end, mid 값을 추가해서 이분탐색을 짰다.

타겟을 모르는데 어떻게 이분 탐색을 써야하는거지? 하고 고민했다. 그런데 투포인터를 계속 돌리면 lt가 rt를 넘어가는 시점이 있기 때문에 결국 이게 최종 값이란 걸 알게 되었다.

전체코드

import sys

r = sys.stdin.readline

k, n = map(int, r().split())

arr = list(int(r()) for _ in range(k))
start = 1
end = sum(arr) / n

while start <= end:
    mid = (start + end) // 2
    count = 0

    for num in arr:
        count += num // mid

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

print(int(end))