[1654/python] 랜선 짜르기

 

 

 현재 가지고 있는 랜선의 갯수와 만들어야 하는 랜선의 갯수가 주어지고 이 후 차례로 현재 가지고 있는 랜선의 길이가 각 줄마다 입력된다. 이 때 원하는 랜선의 갯수를 최대의 길이로 만드는 법을 구해야 한다.

 이 때 답에 해당하는 랜선의 길이는 원하는 랜선의 갯수마다 달라지고 주어지는 랜선의 갯수마다 달라져 쉽게 계산하는 방법은 떠오르지 않아 가능한 랜선의 길이를 탐색하는 이진탐색을 사용하였다. 모든 수를 탐색은 하지만 원하는 특정값 하나만 찾으면 되는 경우였기에 계산이 줄어드는 이진 탐색을 택하였다.

import sys

def main():
    k, n = map(int, sys.stdin.readline().split())
    line = []
    for _ in range(k):
        line.append(int(sys.stdin.readline()))

    left = 1
    right = max(line)
    temp = (left + right) // 2

    while left <= right:
        temp = (left + right) // 2
        answer = 0

        for i in line:
            answer += i //temp

        if answer >= n :
            left = temp + 1
        else:
            right = temp -1

    print(right)


if __name__ == "__main__":
    main()