랜선 자르기

• 파라메트릭 서치로 풀 수 있는 문제
• 길이가 l인 랜선을 최대 몇개 만들수 있는지는, 간단하게 각 랜선을 l로 나눈 몫의 합으로 구할수 있다. 만들수 있는 랜선의 갯수가 N이상이 되는 l의 최댓값을 이분 탐색으로 찾으면 된다.
• 결정 문제를 푸는 데에는 O(K)이 걸린다 (K=랜선의 갯수). 이분탐색의 탐색 범위는 단순하게는 0부터 가장 긴 랜선의 길이까지로 처리해도 충분하다. 조금 더 복잡하게 하면 {전체 랜선의 길이 / 필요한 랜선의 갯수} 로 처리하면 구간의 범위가 O(m)에서 O(m*K/N)로 조금 더 작아지긴 하지만 (m=랜선의 최대 길이, N=필요한 랜선의 개수), 실행시간에는 큰 차이는 없다. 전체 시간복잡도는 O(K*logm) 또는 O(K*log(m*K/N))이 된다.

"""Solution code for "BOJ 1654. 랜선 자르기".

- Problem link: https://www.acmicpc.net/problem/1654
- Solution link: http://www.teferi.net/ps/problems/boj/1654
"""

import sys
from teflib import binsearch


def main():
    K, N = [int(x) for x in sys.stdin.readline().split()]
    lengths = [int(sys.stdin.readline()) for _ in range(K)]

    answer = binsearch.maximum_valid_integer(
        1,
        max(lengths) + 2,
        lambda target_len: sum(l // target_len for l in lengths) >= N)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.binsearch.maximum_valid_integer