문제 바로가기
문제 설명:
산업스파이 민수는 A회사에 위장 취업했습니다. 이를 모르는 민수의 상사는 신입사원 교육 중 일부를 민수에게 맡겼습니다. 민수가 맡은 임무는 신입사원 중 2명을 선발하고 선발된 2명이 같이 공부하게 하는 것입니다. 모든 신입사원들의 능력치는 정수로 표현되어 있는데, 2명의 신입사원이 같이 공부하면 서로의 능력을 흡수하여 두 신입사원의 능력치는 공부 전 두 사람의 능력치의 합이 됩니다. 즉, 능력치가 3과 7인 두 사원이 같이 공부하면 두 사원의 능력치가 모두 10이 됩니다. 선발한 2인의 교육이 끝나면 민수는 다시 2인을 선발하여 교육을 진행할 수도 있습니다. 이때 한번 민수에게 선발된 사원이 다시 선발될 수도 있습니다. 민수가 교육한 신입사원들을 제외한 다른 신입사원들의 능력치는 변하지 않습니다.
민수는 산업스파이이기 때문에 교육 후 모든 신입사원들의 능력치의 합을 최소화하고 싶습니다. 예를 들어, 신입사원들의 능력치가 순서대로 10, 3, 7, 2이며, 민수가 2번 교육을 해야 한다면, 첫 번째 교육은 두 번째 사원과 네 번째 사원을 선발하면 두 사원의 능력치가 5가 되어 신입사원들의 능력치가 10, 5, 7, 5가 됩니다. 두 번째 교육도 두 번째 사원과 네 번째 사원을 선발하면 신입사원들의 능력치는 순서대로 10, 10, 7, 10이 됩니다. 이 경우가 교육 후 모든 신입사원들의 능력치의 합이 37로 최소가 되는 경우입니다.
신입사원들의 능력치를 나타내는 정수 배열 ability와 민수가 교육을 진행해야 하는 횟수를 나타내는 정수 number가 주어졌을 때, 교육 후 모든 신입사원들의 능력치의 합의 최솟값을 return 하는 solution 함수를 완성하세요.
풀이:
푸는데 진짜 얼마 안걸렸다.
최소 합을 구한다. 그러면 우선순위큐를 생각한다. 우선순위큐를 사용하면 제일 작은 값이 맨 앞으로 나온다. (최댓값도 가능)
2개를 뽑아서 더해줘서 다시 그 2개를 heapify 시키면서 넣어준다. 그리고 count += 1을 해준다.
while 문 탈출하면 리스트의 합을 리턴해주면 된다.
import heapq
def solution(ability, number):
heapq.heapify(ability)
count = 0
while count != number:
now1 = heapq.heappop(ability)
now2 = heapq.heappop(ability)
n_now = now1 + now2
heapq.heappush(ability,n_now)
heapq.heappush(ability,n_now)
count += 1
return sum(ability)
댓글