파이썬으로 k개의 동일한 길이 리본을 만들 수 있는 최대 길이 구하기

양의 정수로 이루어진 리스트가 있으며, 각 숫자는 리본의 길이를 나타냅니다. 또한 필요한 리본의 개수를 뜻하는 값 k가 주어집니다. 리본은 원하는 만큼 몇 번이고 잘라낼 수 있으며, 이때 길이 r인 리본을 최소 k개 확보할 수 있는 가장 큰 r을 구하는 것이 목표입니다. 만약 그러한 값이 존재하지 않는다면 -1을 반환해야 합니다.

문제 예시

입력이 ribbons = [1, 2, 5, 7, 15], k = 5라고 가정해 보겠습니다. 이 경우 출력은 5입니다.

그 이유는 다음과 같습니다.

길이 15짜리 리본을 길이 5짜리 조각 3개로 자릅니다.
길이 7짜리 리본은 길이 2와 5로 자릅니다.
원래 길이 5짜리 리본이 하나 있으므로, 결과적으로 길이 5인 리본을 총 5개 얻을 수 있습니다.

접근 방법: 이진 탐색(Binary Search)

이 문제는 이진 탐색으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '길이 r로 k개를 만들 수 있다면, r보다 작은 길이로도 반드시 k개를 만들 수 있다'는 단조성(monotonicity)에 있습니다. 따라서 가능한 길이 범위 [0, 최대 리본 길이] 사이에서 조건을 만족하는 최댓값을 이진 탐색으로 찾아내면 됩니다.

알고리즘 단계

left := 0
right := 리본 길이의 최댓값
left < right인 동안 반복:
- mid := (left + right + 1) // 2 (정수 나눗셈으로 내림)
- 모든 리본에 대해 ribbonLen // mid를 계산한 값들의 합이 k 이상이면:
  - left := mid (더 큰 길이 시도)
- 그렇지 않으면:
  - right := mid - 1 (더 작은 길이 시도)
left가 0이 아니면 left를 반환
그렇지 않으면 -1 반환

여기서 (left + right + 1) // 2처럼 올림 방식으로 중간값을 계산하는 이유는, 조건을 만족할 때 left = mid로 이동하므로 무한 루프에 빠지지 않고 탐색 범위가 항상 좁혀지도록 하기 위함입니다.

구현 예제

다음 구현을 통해 더 잘 이해해 보겠습니다.

def solve(ribbons, k):
    left = 0
    right = max(ribbons)
    while left < right:
        mid = (left + right + 1) // 2
        if sum((ribbonLen // mid for ribbonLen in ribbons)) >= k:
            left = mid
        else:
            right = mid - 1
    if left:
        return left
    return -1

ribbons = [1, 2, 5, 7, 15]
k = 5
print(solve(ribbons, k))

입력

[1, 2, 5, 7, 15], 5

출력

복잡도 분석

이진 탐색은 최대 리본 길이를 M이라 할 때 O(log M)번 반복하며, 매번 n개의 리본에 대해 나눗셈을 수행하므로 전체 시간 복잡도는 O(n log M)입니다. 완전 탐색보다 훨씬 효율적이며, 리본 개수나 길이가 커져도 안정적인 성능을 보장합니다.