국영수

문제 Acmicpc

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapq
import sys
input=sys.stdin.readline
N = int(input())
card_deck = []
for _ in range(N):
    heapq.heappush(card_deck, int(input()))
if len(card_deck)==1: print(0)
else:
    answer=0
    while len(card_deck) > 1:
        k=heapq.heappop(card_deck)+heapq.heappop(card_deck)
        answer+=k
        heapq.heappush(card_deck,k)
    print(answer)

우선순위 큐를 이용해서 2개를 뺀 후 (우선순위 큐에서 heappop하면 가장 작은 것 2개를 빼낸다) 더한 값을 결과값에 누적해서 더해주고, 다시 우선순위 큐에 집어넣는다.

우선순위 큐를 사용하지 않는다면 2개를 더한 값을 넣어준 후 다시 sort()를 쓰던지 해서 정렬시켜야 하는데, 당연히 시간초과가 난다.

어떻게든 우선순위 큐를 안써보려고 해봤지만, 로직대로면 다시 정렬해야 하기에 라이브러리를 사용 안 할수가 없다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n=int(input())
card=sorted([int(input()) for _ in range(n)])
isSet=False
comp_sum=0
comp=0
for idx,i in enumerate(card):
    if isSet==True:
        comp_sum+=(comp_sum+prev+i)
        isSet=False
    else:
        if idx==n-1: comp_sum+=(comp_sum+i)
        prev=i
        isSet=True
print(comp_sum)

위는 틀린 코드인데, 더해서 누적하는 과정은 여차저차 했다고 쳐도 다시 정렬하는 과정이 없기에 당연히 틀린 답이다.

문제를 보고 어떤 로직으로 풀 지, 또 거기에는 어떤 라이브러리가 필요한지 캐치하는 능력을 기르자 (아직 턱없이 부족하다)