백준) 랜선 자르기

문제의 제한사항을 보면 logN으로 풀어야 할 것 같다. 이 경우는 이진 트리, 이분 탐색, 힙 세가지 경우가 자동으로 떠오른다.

 

 

이분 탐색 문제는 양식이 존재하는 느낌이다. dfs처럼 외워야 하는 부분이 있다. bisect를 사용하지 않은 로직으로 비슷하게 푼 문제가 많다.

이분 탐색을 사용하기 위해 배열을 정렬하고 return에 해당하는 부분을 target으로 잡은 뒤 이분탐색을 하면 된다.

import sys

info = list(map(int,sys.stdin.readline()[:-1].split()))
inputs = [int(sys.stdin.readline()[:-1]) for _ in range(info[0])]

inputs.sort()

lo = 1
hi = inputs[-1]
while lo <= hi:
    mid = (lo+hi) // 2

    t1 = 0
    for i in range(len(inputs)):
        if mid <= inputs[i]:
            t1 += inputs[i]//mid

    if t1 >= info[1]:
        lo = mid + 1
    else:
        hi = mid - 1

print(hi)