백준 - 1744: 수 묶기 - Greedy

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

1744번: 수 묶기

세 가지 경우로 나누어 리스트에 저장을 했습니다.

1. 1을 제외한 양의 정수

2. 1

3. 0과 음의 정수

 

그런 후에 1번은 내림차순으로 정렬을 한 뒤 앞에서 부터 묶어주었고, 3번은 오름차순으로 정렬을 한 뒤 앞에서부터 묶어주었습니다.

2번은 1의 개수만큼 값을 더해주었습니다.

 

1번에서 1을 제외한 이유는 1은 곱하는 것보다 더해주는 것이 값을 더 증가시켜주기 때문입니다.

 

3번에서 0과 음의 정수를 묶은 이유는 다음과 같습니다.

3번 리스트를 정렬하게되면 0이 제일 마지막에 오게 됩니다.

배열의 길이가 짝수일 경우 0은 음수와 묶여 곱하게 되고 이는 더하는 것보다 값이 큽니다. (-x + 0 < -x * 0)

배열의 길이가 홀수일 경우는 묶이지 못하고 그냥 0을 더하게 되어 차이가 없습니다.

따라서 제일 작은 음수끼리 곱해지면서 큰 정수 값을 만들다가 마지막에 오는 음수와 0을 곱하거나, 아무 변화가 없게 되는 것입니다.

from sys import stdin
input = stdin.readline

n = int(input())
plus = []
one = []
zero_minus = []

for _ in range(n):
    current = int(input())
    if current > 1:
        plus.append(current)
    elif current == 1:
        one.append(current)
    else:
        zero_minus.append(current)

plus.sort(reverse=True)
zero_minus.sort()
answer = 0

for ii in range(0, len(plus)-1, 2):
    answer += plus[ii] * plus[ii+1]
if len(plus) & 1 == 1:
    answer += plus[-1]

answer += len(one)

for ii in range(0, len(zero_minus)-1, 2):
    answer += zero_minus[ii] * zero_minus[ii+1]
if len(zero_minus) & 1 == 1:
    answer += zero_minus[-1]

print(answer)