이번 문제는 수열의 수들을 양수, 음수, 0으로 구분하여 저장한 뒤에 규칙을 찾아 더하여 가장 큰 결과를 구하여 해결하였다.

처음에는 브루트포스 방식으로 모든 경우를 다 구한 뒤에 그 중 가장 큰 수를 채택해야겠다는 생각을 했지만 매우 비효율적일 것 같다는 생각이 들어서 다른 방법을 고민하던 중 규칙이 있다는 것을 발견했다.

우선 양수, 음수, 0으로 구분하여 저장한 뒤에 절댓값을 기준으로 오름차순 정렬하였다. 그리고 양수는 양수끼리 음수는 음수끼리 연산을 진행했다.

음수의 경우 음수*음수 = 양수가 도출되기 때문에 절댓값이 큰 음수 두개를 골라 곱해주었다. 만약 음수가 2개보다 적을 경우 0이 1개라도 존재하면 선택된 하나의 음수와 0을 곱해 음수를 0으로 없애주었다. 0은 사용했으니 0의 개수를 1 감소시켜준다. 0이 없을 경우에는 선택된 음수를 없애거나 양수로 바꿀 방법이 없으므로 그냥 결과값에 더해주었다.

양수의 경우 1일 경우와 1보다 클 경우로 나누어 생각하였다. 만약 양수 중 하나가 1일 경우 곱한 값보다 더한 값이 더 커지게 되므로 1일 경우에는 두 수의 합을 결과값에 더하도록 해주었고 두 수 모두 1보다 클 경우에는 곱한 값이 더 크므로 곱하여 결과값에 더하도록 해주었다.

음수 * 음수 = 양수
음수 * 0 = 0
==> 음수를 양수로 바꾸거나 0으로 바꿔야 최대값 구할 수 있음
양수 * 1 = 양수
양수 + 1 = 양수 + 1
양수 * 양수 >= 양수 + 양수
==> 1이 있을 경우에는 더해주고 1이 없다면 곱해야 최대값 구할 수 있음

• n을 입력받는다.
• 양수를 저장할 배열 positive를 선언한다.
• 음수를 저장할 배열 negative를 선언한다.
• 0의 개수를 저장할 변수 z를 선언한다.
• 답을 저장할 변수 answer를 0으로 정의한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> 수열의 원소 num을 입력받는다.
  -> 만약 num이 0보다 크다면 positive에 넣는다.
  -> 만약 num이 0보다 작으면 negative에 넣는다.
  -> 만약 num이 0이라면 z를 1 증가시킨다.
• positive를 오름차순 정렬한다.
• negative를 내림차순 정렬한다. (음수이므로 절댓값이 작은 순으로 정렬됨)
• negative의 길이가 0이 아닐 동안 반복하는 while문을 돌린다.
  -> try, except문을 사용하여 예외 처리를 한다. 우선 try문이다.
  --> negative의 가장 뒤에 있는 수를 pop하여 지워주고 a에 대입시킨다.
  --> negative의 가장 뒤에 있는 수를 pop하여 지워주고 b에 대입시킨다.
  (이때 a에는 while문의 조건에 의해 수가 무조건 대입된다.)
  -> try문에 대한 예외 처리를 위한 except문을 돌린다.
  --> 만약 z가 0이 아니라면 b에 0을 대입해주고 z를 1 감소시킨다.
  --> 만약 z가 0이라면 b에 1을 대입해준다. 이는 음수를 그대로 answer에 더해주기 위함이다.
  -> answer에 a*b를 더해준다.
• positive의 길이가 0이 아닐 동안 반복하는 while문을 돌린다.
  -> try, except문을 사용하여 예외 처리를 한다. 우선 try문이다.
  --> positive의 가장 뒤에 있는 수를 pop하여 지워주고 a에 대입시킨다.
  --> positive의 가장 뒤에 있는 수를 pop하여 지워주고 b에 대입시킨다.
  (이때 a에는 while문의 조건에 의해 수가 무조건 대입된다.)
  --> 만약 b가 1이라면 answer에 a+b를 더해준다.
  --> continue 키워드를 통해 while문의 다음 사이클로 넘어간다.
  -> try문에 대한 예외 처리를 위한 except문을 돌린다.
  --> b에 1을 대입시킨다.
  -> answer에 a*b를 더한다.
• answer를 출력한다.

Code

n=int(input())
positive=[]
negative=[]
z=0
answer=0
for i in range(n):
    num=int(input())
    if num>0:
        positive.append(num)
    elif num<0:
        negative.append(num)
    else:
        z+=1
positive.sort()
negative.sort(reverse=True)
while len(negative):
    try:
        a=negative.pop()
        b=negative.pop()
    except:
        if z:
            b=0
            z-=1
        else:
            b=1
    answer+=(a*b)
while len(positive):
    try:
        a=positive.pop()
        b=positive.pop()
        if b==1:
            answer+=(a+b)
            continue
    except:
        b=1
    answer+=(a*b)
print(answer)