백준 온라인 저널, 우선순위 큐, 힙정렬, 그리디 알고리즘/14241번 : 슬라임 합치기(파이썬)

문제

https://www.acmicpc.net/problem/14241

 

문제 정의

영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.

 

모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.

 

영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다.

 

둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다.

 

 

출력

첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다.

 

 

 

 

예제 입력 1

2
3 4

 

예제 출력 1

12

 

 

예제 입력 2

3
2 2 2

 

예제 출력 2

12

 

 

접근 방법

1. 슬라임의 크기에 따라 최대 힙 정렬을 한 뒤, 두 개의 데이터를 뽑고 이를 주어진 식에 따라 계산한다.
2. 계산 후, 다시 최대 힙에 삽입한다. 
3.  이를 반복하다 슬라임이 하나 남았을 때, 그 수를 출력한다.

 

 

 

코드

# 문제 : https://www.acmicpc.net/problem/14241
# 접근 방법
# 슬라임의 크기에 따라 최대 힙 정렬을 한 뒤, 두 개의 데이터를 뽑고 이를 주어진 식에 따라 계산한다.
# 계산 후, 다시 최대 힙에 삽입한다. 
# 이를 반복하다 슬라임이 하나 남았을 때, 그 수를 출력한다.
# 시간복잡도 : O(logN)

import heapq, sys
input = sys.stdin.readline

n = int(input()) # 슬라임 개수 입력받기
slime = list(map(int, input().split())) # 슬라임 크기 입력받기
heap = []
for x in slime:
    heapq.heappush(heap, -x) # 최대 힙 정렬

score = 0 # 점수 초기화
while len(heap) != 1: # 슬라임이 하나남을 때까지 반복
    s1 = heapq.heappop(heap) # 가장 크기가 큰 슬라임 (음수)
    s2 = heapq.heappop(heap) # 두번째로 크기가 큰 슬라임 (음수)
    score += s1*s2 # 점수 계산, 음수 * 음수 = 양수
    heapq.heappush(heap, (s1 + s2)) # 합친 슬라임 다시 삽입하기

print(score) # 점수 출력

- 시간 복잡도 측면에서 봤을 때, 데이터의 개수가 작기 때문에 힙 정렬을 하지 않고 리스트 정렬을 한 뒤에 문제를 풀어도 해결될 것 같다.