[Python] 백준 / gold / 1744번 (수 묶기)

문제 링크 : https://www.acmicpc.net/problem/1744

함정이 있는 문제였다.

(문제 예시)
예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2x3)+(4x5) = 27이 되어 최대가 된다.

알고리즘을 떠올리기는 어렵지 않았다.
minus 리스트와 plus 리스트를 따로 생성하고,
minus와 plus는 절대 서로 곱하는 상황이 발생하면 안된다.

조심해야 할 예외가 있는데,
수열이 {3,1,1} 인 경우 3x1 + 1 = 4가 되는 알고리즘이라는 것이다.
3x1 < 3+1 이므로 1인 경우에는 따로 처리해줘야 했다.

정답 코드

import sys
N = int(input())
plus = []
minus = []

for _ in range(N):
    num = int(sys.stdin.readline())
    if num <= 0: minus.append(num)
    else: plus.append(num)

plus.sort(reverse=True)
minus.sort()
answer = 0

i = 0
while i < len(plus):
    if i+1 < len(plus):
        if plus[i] == 1 or plus[i+1] == 1:
            answer += (plus[i] + plus[i+1])
            i += 2
        else:
            answer += (plus[i] * plus[i + 1])
            i += 2
    else:
        answer += plus[i]
        i += 1

j = 0
while j < len(minus):
    if j+1 < len(minus):
        answer += (minus[j] * minus[j + 1])
        j += 2

    else:
        answer += minus[j]
        j += 1

print(answer)