1654 랜선 자르기

이분탐색 연습문제 - 유독 이분탐색 유형이 어려워서 따로 정리하였다.

오답) 맨 처음 구현

k, n = map(int, input().split())  # k는 10,000까지, n은 1,000,000까지
cables = [int(input()) for _ in range(k)]

cables.sort()

left = 0
right = cables[0]

while True:
    if left > right:
        print(right)
        break
    mid = (left + right) // 2
    divided_cables = [cable // mid for cable in cables]  # 개수
    if (
        sum(divided_cables) < n
    ):  # 너무 몇개 안나온다 싶으면 -> 자르는 단위를 줄여야 한다
        right = mid - 1
    else:
        left = mid + 1

‼️ 틀린 부분 1 : left를 0으로 잡은 것

이분탐색 대표 예시에서는 이분 탐색의 대상이 특정 리스트의 포인터였기 때문에, left를 0으로 설정한 거였음.
그거만 기억나서 left를 0으로 설정했으나, 이번에는 특정한 수를 찾는 것이기 때문에 left를 0으로 설정할 경우 ZeroDivisionError가 발생할 수 있음.

‼️ 틀린 부분 2 : right를 주어진 랜선의 최솟값으로 잡은 것

이건 문제 이해를 잘못한 거였음.. 반드시 모든 선을 잘라야 할 필요는 없다..

정답 (위의 틀린 부분들 수정)

k, n = map(int, input().split())  # k는 10,000까지, n은 1,000,000까지
cables = [int(input()) for _ in range(k)]

cables.sort()

left = 1
right = cables[-1]

while True:
    if left > right:
        print(right)
        break
    mid = (left + right) // 2
    divided_cables = [cable // mid for cable in cables]  # 개수
    if (
        sum(divided_cables) < n
    ):  # 너무 몇개 안나온다 싶으면 -> 자르는 단위를 줄여야 한다
        right = mid - 1
    else:
        left = mid + 1