728x90
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에
www.acmicpc.net
분석
- 양수 : 가능한 큰 수들끼리 묶음
- 음수: 음수끼리 곱해서 양수로 더함
- 0 : 음수가 남는경우 0을 곱함
- 1 : 다 더함
풀이
import sys
input=sys.stdin.readline
from queue import PriorityQueue
pq = PriorityQueue() # 양수처리
mq = PriorityQueue() # 음수처리
one=0
zero=0
n=int(input())
for _ in range(n):
data=int(input())
if data>1:
pq.put(data*-1) # 내림차순 정렬을 위해 -1을 곱해서 저장
elif data==1:
one+=1
elif data==0:
zero+=1
else:
mq.put(data)
sum=0
# 양수 처리
while pq.qsize() > 1:
tmp= pq.get()*pq.get()
sum+=tmp
if pq.qsize() > 0:
sum+=pq.get()*-1
# 음수 처리
while mq.qsize() > 1:
tmp = mq.get()*mq.get()
sum += tmp
# 음수 큐에 데아터 남아있고 0이 한개도 없으면
if mq.qsize() > 0:
if zero==0:
sum+=mq.get()
sum+=one
print(sum)
728x90