파이썬에서 같은 길이의 리본의 최대 길이를 찾는 프로그램

<시간/>

리본 길이를 나타내는 양수 목록과 하나의 값 k가 있다고 가정합니다. 우리는 원하는 만큼 리본을자를 수 있습니다. 길이가 r인 k개의 리본을 가질 수 있도록 가장 큰 길이 r을 찾아야 합니다. 이러한 솔루션을 찾을 수 없으면 -1을 반환합니다.

따라서 입력이 리본 =[1, 2, 5, 7, 15] k =5와 같으면 크기 15의 리본을 길이가 5인 3개의 조각으로자를 수 있으므로 출력은 5가 됩니다. 그런 다음 크기 7의 리본을 크기 2와 5로 자릅니다. 그리고 크기 5의 리본이 하나 더 있으므로 크기 5의 리본이 총 5개 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

왼쪽 :=0
오른쪽 :=최대 리본
왼쪽 <오른쪽, do
- 중간:=(왼쪽 + 오른쪽 + 1) / 2의 바닥
- 목록에 있는 모든 요소의 합이 (최소 k인 리본의 각 ribbonLen에 대한 ribbonLen / mid의 바닥),
  - 왼쪽 :=중간
- 그렇지 않으면
  - 오른쪽 :=중간 - 1
왼쪽이 0이 아니면
- 좌회전
반환 -1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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