[백준] 1744번 수 묶기

문제 설명

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

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

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

제한 사항

-첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작은 자연수이다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

​-수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

​

입출력 예

input	output
4 -1 2 1 3	6

​

접근법

어떤 조건일 때에 곱하는게 더 클지에 대해서 생각해봅시다. 먼저 자연수인 경우에는 내림차순으로 정렬한 뒤, 앞에서부터 두개씩 짝지어 곱하는게 훨씬 큽니다. 반면, 음수인 경우에는 오름차순으로 정렬한 뒤, 앞에서부터 두개씩 짝지어 곱하는게 훨씬 큽니다. 이를 이용하여 구현하면 다음과 같습니다.

​

나의 코드

import sys

number = int(sys.stdin.readline())
num_list = []
for _ in range(number):
    num_list.append(int(sys.stdin.readline()))
num_list.sort(reverse=True)
num_sum = 0
while len(num_list) > 0:
    if num_list[0] <= 0:
        num_list.sort()
    if len(num_list) == 1:
        num_sum += num_list.pop()
    else:
        if num_list[0] < (num_list[0] * num_list[1]):
            num_sum += (num_list.pop(0) * num_list.pop(0))
        else:
            num_sum += num_list.pop(0)
print(num_sum)