백준 - 1774번(정렬, 그리디)

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

import sys

n = int(sys.stdin.readline())

p_arr = [] #양수들의 집합
n_arr = [] #음수들의 집합
cnt = 0

for _ in range(n):
    x = int(sys.stdin.readline())
    if x>0:
        p_arr.append(x)
    elif x<0:
        n_arr.append(x)
    else:
        cnt = cnt + 1 #0은 존재하는지 존재하지 않는지만 신경 쓰면 된다.

p_arr.sort()
n_arr.sort(reverse=True)

p_ans = 0
n_ans = 0

#양수 집합의 최대합 판별
if len(p_arr) % 2 == 0:
    for i in range(0,len(p_arr),2):
        if p_arr[i]*p_arr[i+1] > p_arr[i] + p_arr[i+1]:
            p_ans = p_ans + (p_arr[i]*p_arr[i+1])
        else:
            p_ans = p_ans + (p_arr[i] + p_arr[i + 1])
else:
    while p_arr:
        if len(p_arr) == 1:
            p_ans = p_ans + p_arr[0]
            break
        a = p_arr.pop()
        b = p_arr.pop()
        if a*b > a+b:
            p_ans = p_ans + a*b
        else:
            p_ans = p_ans + a + b

#음수 집합의 최대합 판별
if len(n_arr)%2 == 0:
    for i in range(0,len(n_arr),2):
        if n_arr[i] * n_arr[i + 1] > n_arr[i] + n_arr[i + 1]:
            n_ans = n_ans + (n_arr[i]*n_arr[i+1])
        else:
            n_ans = n_ans + (n_arr[i] + n_arr[i + 1])
else:
    while n_arr:
        if len(n_arr) == 1:
            if cnt == 0:
                n_ans = n_ans + n_arr[0]
                # 만약 cnt가 0이라면 수열 안에 0이 한개도 존재하지 않기 때문에 
                # 남은 음수 하나를 0으로 바꿔주지 못하고 더해줘야 한다.
            break
        a = n_arr.pop()
        b = n_arr.pop()
        if a * b > a + b:
            n_ans = n_ans + a * b
        else:
            n_ans = n_ans + a + b

print(n_ans + p_ans)

해당 문제는 두 개씩 묶어서 최대합을 만드는 문제이다.

일단 양수는 오름차순으로 정렬해서 큰 수끼리 묶을수록 더 큰 값이 나온다는 사실을 쉽게 생각할 수 있다.

음수 역시 음수*음수 = 양수 이므로 절대값이 큰 음수끼리 묶으면 최댓값이 나온다는 사실을 알 수 있다.

만약에 음수의 개수가 홀수일 경우 가장 작은 음수가 하나 남게 된다.

이때 cnt를 보고 만약 0이 한개라도 존재한다면 해당 0을 곱해주면 남은 음수 하나는 0으로 바뀌고 값에 영향을 미치지 않는다.

0이 여러개 있다고 하더라도 0*0=0 이기 때문에 값에 직접적인 영향을 미치지 않는다.

즉  결과적으로 음수는 안 남거나 무조건 한 개가 남을 것이다.

이때 음수가 한 개가 남았을때 0이 한개 이상 존재한다면 음수를 더해주는 것보다 0을 더해주는 게 결괏값이 더 커진다.

이 부분을 생각하면 쉽게 풀 수 있다.