우주의 IT 소행성

수열을 묶어 최대의 값을 가져오는 문제 (그리드)

어떤 경우에 최대 값이 나올 수 있는가에 대해 생각 해보자.

입력 된 값들을 오름차순으로 정렬했을 때

앞부분에 [음수, 0, 1]에 해당하는 값이 나온다면 이 값을 우선 계산해주어야 한다.

0번째와 1번째의 값 비교

음수, 음수 -> 곱한다

음수, 0 -> 곱한다

음수, 양수 -> 더한다

이렇게 앞부분의 양수가 아닌 값( 1 제외 )을 없애준 후

나머지는 뒤에서부터(큰 순서로) 2개씩 묶어 곱해주면 된다.

ex) -1 2 1 3일 경우

정렬하면 -1 1 2 3

-1과 2는 (음수, 양수)이기에 더해준다. -> 0

뒤에 2, 3을 묶어 곱해준다 -> 6

0 + 6 -> 6

n = int(input())
data = list(int(input()) for _ in range(n))
data.sort()

result = 0
while True:
    if len(data) == 0:
        break
    elif len(data) == 1:
        result += data.pop(0)
        break
    elif data[0] == 0 and len(data) >= 2:
        result += data.pop(0) + data.pop(0)
    elif data[0] < 0 and len(data) >= 2:
        tmp1 = data.pop(0)
        tmp2 = data.pop(0)
        if tmp2 < 0:
            result += tmp1 * tmp2
        elif tmp2 > 0 and (len(data) + 2) % 2 == 0:
            result += tmp1 + tmp2
        elif tmp2 > 0 and (len(data) + 2) % 2 == 1:
            data.insert(0, tmp2)
            data.insert(0, tmp1)
            tmp1 = data.pop()
            tmp2 = data.pop()
            result += tmp1 * tmp2

    elif len(data) >= 2:
        tmp1 = data.pop()
        tmp2 = data.pop()
        if tmp1 == tmp2 == 1:
            result += tmp1 + tmp2
        elif tmp1 == 1 or tmp2 == 1:
            result += tmp1 + tmp2
        else:
            result += tmp1 * tmp2
print(result)