[백준] 수 묶기

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

1744번: 수 묶기

 

간단하게 생각해보면 같은 부호끼리는 절댓값이 큰 순서대로 묶어서 계산해야 최댓값이 된다. 양수하고 음수를 묶어야 할 상황에는 묶지 말고 더하는 것이 최댓값이 된다.

 

주의해야 할 점은 1과 0이다. 1은 무조건 더하는 것이 최댓값이 된다. 그리고 0은 양수랑 남으면 더하는 것이 최대지만, 음수랑 남으면 묶어서 계산하는 것이 최댓값이 된다.

 

그래서 우선순위 큐를 이용하여 부호에 따라 담을 큐를 두 개 만들고 0은 queue_nonplus 에 담는다. 1은 더하는 것이 최대이므로 미리 더해서 queue_plus 에 담지 않는다.

 

import sys
import heapq

N = int(sys.stdin.readline())
queue_plus = []
queue_nonplus = []
answer = 0

for i in range(N):
    n = int(sys.stdin.readline())

    if n == 1:
        answer += 1
    else:
        heapq.heappush(queue_plus, -n) if n > 0 else heapq.heappush(queue_nonplus, n)

while queue_plus:
    if len(queue_plus) > 1:
        a = heapq.heappop(queue_plus)
        b = heapq.heappop(queue_plus)
        answer += (a * b)
    else:
        answer -= heapq.heappop(queue_plus)

while queue_nonplus:
    if len(queue_minus) > 1:
        a = heapq.heappop(queue_nonplus)
        b = heapq.heappop(queue_nonplus)
        answer += (a * b)
    else:
        answer += heapq.heappop(queue_nonplus)

print(answer)