[BOJ] Q1744 수 묶기

[BOJ] Q1744 수 묶기

Question

Language: Python

Difficulty: Gold 4

곱셈을 하게 되었을 때 양수가 나오는 조합은 아래와 같다. 양 * 양 음 * 음

이러한 특성을 이용해서 해당 문제는 음수,양수로 이루어져 있는 부분을 분리해서 생각해야한다. 단, 1에 대해서는 곱셈을 진행하면은 안된다. 항상 1을 곱하는 경우는 더하는 경우보다 작게 나오기 때문이다.

만약, 0이 포함되는 경우, 0은 남는 음수에 대해서 곱해주면, 음수를 없앨 수 있다.

Solution

from heapq import heappush, heappop

def solution():
    result=0

    plus_group=[]
    minus_group=[]
    zero_count=False

    for number in numbers:
        if number > 0 :
            heappush(plus_group,-number)
        elif number < 0:
            heappush(minus_group,number)
        else:
            zero_count=True
    
    #양수 처리
    while len(plus_group) >=2:
        op1=-(heappop(plus_group))
        op2=-(heappop(plus_group))
        #1은 곱하지 않는다
        if op1 ==1 or op2 ==1:
            result+=(op1+op2)
            break

        result+=op1*op2

     #남아 있는 양수 값은 더한다
    result-=sum(plus_group)

    #음수 처리
    while len(minus_group) >=2:

        op1=heappop(minus_group)
        op2=heappop(minus_group)
        
        result+=op1*op2
        
    #만약 0이 있게 되면 이는 음수와 곱해서 0으로 만드는것이 가장 큰 값을 만든다.
    if not zero_count:
        result+=sum(minus_group)
    
    return result
if __name__ == "__main__":
    N=int(input())
    numbers=[int(input()) for _ in range(N)]
    
    print(solution())