📚 2036 - 수열의 점수

수열의 점수

이해

n개의 정수로 이루어진 수열이 있다.

• 한 정수를 제거할 수 있다.
• 두 정수를 제거할 수 있다.

한 정수를 제거하는 경우 그 정수가 점수
두 정수를 제거하는 경우 두 정수의 곱이 점수

수열에 아무 수도 남지 않게 되었을 때, 점수의 총 합의 최대를 구하는 프로그램

이와 같은 문제들을 풀 때 규칙이 있다.
두 정수를 제거하는 경우 두 정수의 곱의 점수가 최대한 많이 사용되어야 한다.
음수와 0을 하나의 조합, 양수를 하나의 조합으로 주면 된다.
1같은 경우 갯수만큼 덧셈을 해줘야한다. (1같은 경우 곱셈보다 덧셈이 더 큰 값을 얻을 수 있다.)

ex)

-5 -4 -3 -2 -1 2 3 4 7 8

음수, 0 : -5 -4 -3 -2 -1
양수 : 8 7 4 3 2

-1, 2를 제외하고 나머지는 순차적으로 곱셈해서 더한다.

소스

import sys  
  
read = sys.stdin.readline  
  
n = int(read())  
  
positive = []  
negative = []  
  
answer = 0  
  
for i in range(n):  
    num = int(read())  
  
    if num <= 0:  
        negative.append(num)  
    elif num == 1:  
        answer += 1  
    else:  
        positive.append(num)  
  
negative.sort()  
positive.sort(reverse=True)  
  
  
firstlen = len(negative)  
secondlen = len(positive)  
if len(negative) % 2:  
    answer += negative[firstlen - 1]  
    firstlen -= 1  
  
if len(positive) % 2:  
    answer += positive[secondlen - 1]  
    secondlen -= 1  
  
for i in range(0, firstlen, 2):  
    answer += negative[i] * negative[i + 1]  
  
for i in range(0, secondlen, 2):  
    answer += positive[i] * positive[i + 1]  
  
print(answer)