[백준] 랜선 자르기 1654번 - Python

[백준] 랜선 자르기 1654번

나의 풀이

import sys
N, K = map(int, sys.stdin.readline().split())
nums = []
for i in range(N):
    nums.append(int(sys.stdin.readline()))
def binary_search(start, end):
    while start <= end:
        total = 0
        mid = (start + end) // 2
        for x in nums:
            total += x // mid
        if total >= K:
            start = mid + 1
        elif total < K:
            end = mid - 1
    return end

print(binary_search(1, max(nums)))

• 입력받은 숫자들 중에서 가장 큰 숫자를 끝으로 잡고 이분 탐색을 돌린다.
• 중간 값으로 잘랐을 경우 랜선의 개수를 계산해준다.
• 랜선의 개수가 K 보다 많거나 같다면 start 를 mid + 1 해준다. 같다면 조건을 넣어줘야 최대값을 구할 수 있다.
• 랜선의 개수가 K 보다 적다면 end 를 mid - 1 해준다.
• 랜선의 개수가 많다는 것은 랜선의 길이를 짧게 잡았다는 뜻이고, 랜선의 개수가 적다는 것은 랜선의 길이를 길게 잡았다는 의미이다.
• 그렇게 해서 start 가 end 보다 커지면 반복이 종료되는데 이 때 end 가 만족하는 값 중 최대값이 된다.