Python에서 구조에 필요한 최소 로켓 수를 찾는 프로그램

<시간/>

무게라고 하는 숫자 목록이 있고 이것이 사람들의 무게를 나타내고 값 제한이 로켓 한 척의 무게 제한을 결정한다고 가정합니다. 이제 각 로켓에는 최대 2명이 탑승할 수 있습니다. 우리는 모두를 행성으로 구출하는 데 필요한 최소한의 로켓 선박 수를 찾아야 합니다.

따라서 입력이 weight =[300, 400, 300], limit =600과 같으면 출력은 2가 됩니다. 각각의 무게가 300인 두 사람을 태우려면 로켓 한 척이 필요하고 다른 두 사람을 데려가려면 다른 로켓이 필요하기 때문입니다. 체중이 400인 사람.

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

목록 가중치 정렬
cnt :=0
가중치가 비어 있지 않은 동안 수행
- x :=가중치에서 마지막 요소 삭제
- weights가 비어 있지 않고 weights[0] <=limit − x이면
  - 가중치에서 첫 번째 요소 삭제
- cnt :=cnt + 1
반환 cnt

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

예시(파이썬)

class Solution:
def solve(self, weights, limit):
   weights.sort()
   cnt = 0
   while weights:
      x = weights.pop()
      if weights and weights[0] <= limit - x:
         weights.pop(0)
      cnt += 1
   return cnt
ob = Solution()
weights = [300, 400, 300]
limit = 600
print(ob.solve(weights, limit))

입력

[300, 400, 300], 600