[백준] q1744 수 묶기

문제

길이가 N인 수열이 주어졌을 때, 수열의 각 수를 묶게 되면 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 적절히 묶어서 그 합이 최대가 되게 하는 프로그램을 작성하라.

어떻게 풀 것인가?

수열의 수를 음수, 양수, 0, 1로 분리하여 각각 저장한다.

양수의 경우 가장 큰 값부터 묶어서 곱한 후에 더한다. 양수의 개수가 홀수라면, 마지막 요소를 더한다.

음수의 경우 가장 작은 값부터 묶어서 곱한 후에 더한다. 음수의 개수가 홀수라면, 마지막 요소를 더한다.

1은 묶어서 곱하는 것보다 더하는 것이 합을 최대가 되게 한다.

0이 존재하고 음수의 개수가 홀수라면, 마지막 요소와 곱하여 상쇄시킬 수 있다.

N = int(input())
pp = []
nn = []
ee = []
for _ in range(N):
    tmp = int(input())
    if tmp > 1:
        pp.append(tmp)
    elif tmp < 0:
        nn.append(tmp)
    else:
        ee.append(tmp)

pp.sort(reverse=True)  # 양수로만 구성된 수열은 내림차순
nn.sort()  # 음수로만 구성된 수열은 오름차순

l_pp = len(pp)  # 양수의 개수
l_nn = len(nn)  # 음수의 개수
l_ee = len(ee)  # 1 또는 0의 개수

answer = 0
if l_pp % 2 == 0:  # 양수 요소의 개수가 짝수라면
    for i in range(0, l_pp-1, 2):
        answer += pp[i] * pp[i + 1]  # 모두 묶어서 더하기
else:  # 양수 요소의 개수가 홀수라면
    for i in range(0, l_pp-1, 2):
        answer += pp[i] * pp[i + 1]
    answer += pp[-1]  # 마지막 요소 더하기

if l_nn % 2 == 0:  # 음수 요소의 개수가 짝수라면
    for i in range(0, l_nn-1, 2):
        answer += nn[i] * nn[i + 1]  # 모두 묶어서 더하기
else:
    for i in range(0, l_nn-1, 2):  # 음수 요소의 개수가 홀수라면
        answer += nn[i] * nn[i + 1]
    if 0 in ee:  # 마지막 요소 더하기
        answer += 0 * nn[-1]
    else:
        answer += nn[-1]

for e in ee:  # 1 더하기
    answer += e
print(answer)