BOJ 1654 - 랜선 자르기

문제

백준 온라인 저지 - 1654번

풀이 과정

랜선들을 일정한 크기로 잘랐을 때 원하는 개수를 만족하는 최대 길이를 찾는 문제입니다.

랜선 길이의 상한과 하한을 결정한 뒤 이분 탐색 을 통해 알맞은 길이를 찾을 수 있습니다.
랜선 길이의 상한은 가지고 있는 랜선 중 가장 긴 값이고 하한은 1로 설정해서 문제를 해결하였습니다.

코드

import sys


K, N = list(map(int, sys.stdin.readline().split()))
lines = []
for _ in range(K):
    lines.append(int(input()))


def enough(cut):
    ret = 0
    for line in lines:
        ret += line // cut
    return True if ret >= N else False


def solution():
    lo = 1
    hi = max(lines)

    answer = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if enough(mid):
            answer = mid
            lo = mid + 1
        else:
            hi = mid - 1

    return answer


print(solution())