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

www.acmicpc.net/problem/1654

import sys
input = sys.stdin.readline


def getLanCountAfterCut(lans, cutBy):
    lanCountAfterCut = 0
    for lan in lans:
        lanCountAfterCut += lan//cutBy
    return lanCountAfterCut


K, N = map(int, input().split())
lans = [int(input()) for _ in range(K)]

left, right = 1, max(lans)
while left <= right:
    mid = (left+right)//2
    lanCountAfterCut = getLanCountAfterCut(lans, mid)

    if N <= lanCountAfterCut:
        left = mid+1
    else:
        right = mid-1
print(right)

가장 큰 랜선의 길이를 right로 두고 이진탐색을 진행하면 된다.

각 mid 값에 대해, 일정 값으로 모든 랜선을 나눌 시 총 몇 개로 나누어지는지를 계산하는 함수를 만들어서, 여기에 mid를 넣어준다.

그리고 최대 길이를 출력해야하므로, if문이 N <= lanCountAfterCut이 되었다. 이렇게 하면 lanCountAfterCut이 같은 영역 안에서 가장 인덱스가 큰 곳으로 향하기 때문이다.