백준 1654번: 랜선 자르기 (파이썬, 이분탐색)

랜선을 잘라서 N개의 랜선을 만들어야 한다. 시작값을 1로 설정하고, N이 1일때는 랜선중에 가장 큰값을 써야하기때문에 max(랜선)을 끝값으로 설정하였다.

 

그 후 입력으로 받은 랜선들을 각각 중간값으로 나누어 그 몫을 더하고, 그 값이 N보다 크면 시작값을 중간값으로 하여 몫들의 합이 더 작아지게 한다.

import sys

K, N = map(int, sys.stdin.readline().split())
wires = []
for i in range(K):
    wires.append(int(sys.stdin.readline()))

start, end = 1, max(wires)

while start <= end:
    cnt = 0
    mid = (start+end) // 2
    for wire in wires:
        cnt += (wire // mid)
    if cnt >= N:
        start = mid + 1
    else:
        end = mid - 1

print(end)