[백준 1654] 랜선 자르기(Python)

1. 아이디어

이분탐색으로 해결하는 것은 알겠는데, left와 right를 무엇으로 설정해야할까. 문제를 다시 읽어보자. 요구사항은 K개의 랜선들을 N개이상의 랜선으로 자를 때, 나올 수 있는 최대 길이를 구하는 것이다.(여기서 K <= N)

다시 말해, 길이를 찾는 문제이므로 길이를 left, right로 설정하면된다. 정답으로 가능한 길이 중 최소 길이는 1이므로 left는 1이되고, right는 입력으로 주어진 랜선 중 길이가 가장 긴 것으로 하면된다.

이후 이분탐색을 진행하고, 입력으로 주어진 각 랜선의 길이를 mid(자를 랜선 길이)로 나누고 그 결과를 합한다.(i.e. 랜선의 개수) 이후, 랜선의 개수가 N개 이상이고 최대 길이인지 여부를 확인한다.

만약 자른 랜선의 개수가 N이상이면, 랜선을 짧은 단위로 자른 것을 의미하므로, 자를 랜선 길이를 높인다.(i.e. left = mid + 1) 반대로, 자른 랜선의 개수가 N미만이면, 랜선을 긴 단위로 자른 것을 의미하므로, 자를 랜선 길이를 줄인다.(i.e. right = mid - 1)

2. 코드

import sys

k , n = map(int, sys.stdin.readline().rsplit())
arr = []
for _ in range(k): arr.append(int(sys.stdin.readline().rstrip()))

arr.sort()
answer = 0
left, right = 1, arr[-1]

while left <= right:
    mid = (left + right) // 2
    count = 0
    for num in arr: count += num // mid

    if count >= n:
        answer = max(answer, mid)
        left = mid + 1
    
    else: right = mid - 1

print(answer)