[백준] 1744번 - 수 묶기

아이디어

예제를 통해 0,1,음수가 이 문제의 키포인트라는 것을 알 수 있었다.
따라서, 수열을 입력받을 때부터 음수, 양수, 0,1값을 나눠서 저장해서 처리하였다.
1. 음수값이 2개이상 있을 경우, 묶어서 곱하면 양수값이 되기 때문에 오름차순 정렬(절댓값이 큰 값을 먼저 처리할 수 있도록)하였다.
2. 0의 경우, 음수값과 곱하였을 때, 음수값을 무력화시킬 수 있기 때문에 음수가 홀수개일 경우, 가장 큰 음수값을 0과 곱해서 무력화 시켜주었다.
3. 1의 경우, x값과 곱할 경우 x값이 되기 때문에 1은 묶어서 곱하는 것보다 값을 더하는 것이 이득이다. 따라서, 1은 다른 모든 계산이 마무리된 후에 1의 개수만큼 더해주었다.

코드

# 수 묶기
# 중요한 키포인트 지점 - 음수, 0, 1

N = int(input()) # 수열의 크기

# 수열 입력받기 (음수, 양수,0,1 분리)
negative = []
positive = []
zero = 0
one = 0
for _ in range(N):
    num = int(input())
    if num < 0: # 음수에 0 포함한 이유 - 음수 개수에 따라서 0을 없앨지 곱할지 판단하기 위함
        negative.append(num)
    elif num == 0:
        zero += 1
    elif num == 1:
        one += 1
    elif num > 1:
        positive.append(num)

# 음수 정렬 - 오름차순
negative = sorted(negative)
# 양수 정렬 - 내림차순
positive = sorted(positive,reverse=True)

result = 0

# 음수, 0 처리
negative_len = len(negative)
if negative_len % 2 == 0: # 음수 짝수개 -> 2개씩 묶기
    for i in range(0,negative_len,2):
        result += negative[i] * negative[i+1]
elif negative_len % 2 == 1: # 음수 홀수개 -> 2개씩 묶고 나머지는 0의 개수에 따라서 더할지 말지 결정하기
    for i in range(0,negative_len-1,2):
        result += negative[i] * negative[i+1]
    if zero == 0: # 0인 값이 없으면 음수랑 0을 곱할 수 없기 때문에 마지막 음수값을 더해줘야 한다
        result += negative[-1]

# 양수 처리
positive_len = len(positive)
if positive_len % 2 == 0:
    for i in range(0,positive_len,2):
        result += positive[i] * positive[i+1]
elif positive_len % 2 == 1:
    for i in range(0,positive_len-1,2):
        result += positive[i] * positive[i+1]
    result += positive[-1] # 마지막 값 더해주기

# 1 처리
if one > 0:
    result += one
print(result)