Search

PGS 신입사원 교육

URL
태그
그리디 알고리즘
자료 구조
우선순위 큐

문제 설명

•
신입사원들의 능력치 배열과 교육 횟수가 주어질 때, 두 명의 능력치를 반복적으로 합쳐 모든 신입사원들의 능력치 합을 최소화하는 값을 구하는 문제

예제 입력/출력

ability
number
result
[10, 3, 7, 2]
2
37
[1, 2, 3, 4]
3
26

제약 조건

•
2≤∣ability∣≤1,000,0002 ≤ |ability| ≤ 1,000,000
•
1≤number≤10,0001 ≤ number ≤ 10,000

문제 풀이

접근1 브루트 포스 - O(number⋅∣ability∣2)O(number \cdot |ability|^2)
접근2 그리디 - O(number⋅log∣ability∣)O(number \cdot log |ability|)

풀이 코드

import heapq def solution(ability, number): # 우선순위 큐 구성 hq = [] for n in ability: heapq.heappush(hq, n) # min-heap을 사용해 그리디하게 작은 값 2개씩 선택 for _ in range(number): num1 = heapq.heappop(hq) num2 = heapq.heappop(hq) sum_num = num1 + num2 heapq.heappush(hq, sum_num) heapq.heappush(hq, sum_num) return sum(hq)
Python
복사