백준 1654 랜선 자르기(with Python)

어떤 문제?

제목에 적힌 문제입니다.

이분 탐색을 활용하는 문제입니다.

내가 생각한 Solution

문제에서 생각해볼 점

• 저는 처음에 가장 짧은 랜선을 기준으로 이분탐색을 수행했습니다. 하지만 이런 경우 가장 긴 랜선만 자르는 경우를 고려할 수 없습니다.

• 또한 가장 긴 랜선을 기준으로 이분탐색을 수행해야 모든 경우를 살필 수 있을 것입니다.

코드 구현

import sys
K, N = map(int, sys.stdin.readline().split())

arr = [0] * K
for i in range(K):
    arr[i] = int(sys.stdin.readline().strip())

r = max(arr)
l = 1

while True:
    cnt = 0
    mid = (l+r) // 2
    if r-l < 0:
        break
    for i in range(K):
        cnt += arr[i] // mid
    if cnt >= N:
        l = mid+1
    else:
        r = mid-1

print(r)