[python] 백준 1744 수 묶기

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

1744번: 수 묶기

 

문제 해결

1보다 큰 양수는 더하는 것 보다 곱하는 것이 이득

1은 더하는 것이 이득

0은 아무런 영향이 없지만 음수가 있을때 음수를 곱해주면 0을 만들 수 있다.

음수는 음수끼리 곱하면 양수가 된다.

우선순위 큐를 통해 1보다 큰 양수, 음수를 따로 리스트를 분리해서 배열한 후 그 안에서 각각 절대값이 큰 것끼리 곱한다.

양수 리스트에 수가 남으면 더한다.

음수 리스트에 수가 남았고 0인 수가 있으면 곱해서 0으로 만든다. (없으면 더한다.)

 

CODE

import sys
import heapq
n = int(input())
p = []
m = []
one = 0
zero = 0
for i in range(n):
    x = int(input())
    if x == 1:
        one +=1
    elif x == 0:
        zero += 1
    elif x>=2:
        heapq.heappush(p,-x)
    else:
        heapq.heappush(m,x)
ans = one
while len(p)>1:
    a = heapq.heappop(p)
    b = heapq.heappop(p)
    ans += a*b
while len(m)>1:
    a = heapq.heappop(m)
    b = heapq.heappop(m)
    ans += a*b
if len(p):
    r1 = heapq.heappop(p)
    ans += abs(r1)
if len(m):
    if zero==0:
        r2 = heapq.heappop(m)
        ans += r2
print(ans)