nums라는 숫자 목록이 있다고 가정합니다. 임의의 두 숫자를 제거하고 끝에 합을 추가하여 num의 길이를 줄일 수 있습니다. 이 작업을 수행하는 비용은 우리가 제거한 두 정수의 합입니다. 숫자를 하나의 정수로 줄이는 데 필요한 최소 총 비용을 찾아야 합니다.
따라서 입력이 nums =[2, 3, 4, 5, 6]과 같으면 2와 3을 취한 다음 [4, 5, 6, 5]를 얻기 위해 제거하므로 출력은 45가 됩니다. 4와 5를 취한 다음 제거하여 [6, 5, 9]를 얻은 다음 6과 5를 취한 다음 제거하고 [9, 11]을 얻고 마지막으로 9와 11을 제거하면 19를 얻습니다. 따라서 합계는 45.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- num에 있는 요소를 사용하여 힙 만들기
- ans :=0
- 숫자 크기>=2, do
- a :=힙 번호의 최상위 요소
- b :=힙 번호의 최상위 요소
- ans :=ans + a + b
- 힙 번호에 a+b 삽입
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, nums): import heapq heapq.heapify(nums) ans = 0 while len(nums) >= 2: a = heapq.heappop(nums) b = heapq.heappop(nums) ans += a + b heapq.heappush(nums, a + b) return ans ob = Solution() nums = [2, 3, 4, 5, 6] print(ob.solve(nums))
입력
[2, 3, 4, 5, 6]
출력
45