악곱 == 악성곱슬

그리디

---

해당 문제를 그리디로 접근한 정당성은 다음과 같다.

• 두 수씩 곱하고 이를 더해서 최대를 구해야 한다, 그런데 두 수를 주어진대로가 아닌 리스트에서 아무거나 두 개를 뽑아서 더하면 된다. 한 번 곱한 수는 다시 사용할 수 없다.
• 따라서 정렬을 하면 되겠다는 생각 → 음수도 곱해도 양수가 되니 음수는 음수끼리 곱해야 겠다는 생각 → 두 개의 리스트로 만들어서, 절대값이 큰 순서로 내림차순 정렬을 하고 두 개씩 인덱스를 넘기며 탐색하면 최적의 해가 나올 것이라는 판단

0은 음수와 곱하면 -부호가 사라지는 역할을 하기 때문에 음수 리스트에 추가

처음에는 1을 양수 리스트에 추가 했다가 1, 2 인 경우 1*2 를 해버려서 결과가 2가 나와서 틀렸다. 최대 값은 1은 그냥 더하는 1 + 2 인데 이 점을 디버깅 하는데 꽤 오랜 시간이 걸렸다.

따라서 1은 리스트에 넣지 않고 그냥 바로 결과에 더해주었다.

import sys

def solution(seq, n):
    answer = 0
    positive_seq = list()
    negative_seq = list()
    for num in seq:
        if num <= 0:  # 0은 음수랑 곱하면 0이 되므로 여기에 포함
            negative_seq.append(num)
        elif num > 1:  # 1은 그냥 더하는게 곱하는거보다 크다
            positive_seq.append(num)
        else:           # 1은 그냥 더한다.
            answer += 1

    positive_seq.sort(reverse=True)
    negative_seq.sort()

    p_seq_len = len(positive_seq)
    n_seq_len = len(negative_seq)

    for i in range(1, p_seq_len, 2):
        answer += positive_seq[i] * positive_seq[i-1]
    if p_seq_len % 2 == 1:  # 배열 길이가 홀수면 마지막 원소 더함
        answer += positive_seq[-1]

    for i in range(1, n_seq_len, 2):
        answer += negative_seq[i] * negative_seq[i-1]
    if n_seq_len % 2 == 1:  # 배열 길이가 홀수면 마지막 원소 더함
        answer += negative_seq[-1]

    return answer

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    _seq = list()
    for _ in range(N):
        _seq.append(int(sys.stdin.readline().rstrip()))
    print(solution(_seq, N))