백준 / 1744 수 묶기 python3

www.acmicpc.net/problem/1744

1744번: 수 묶기

수열이 주어졌을 때 주어진 수들을 한 번만 묶거나 안 묶을 수 있다.

묶인 수는 곱해서 더하고 안 묶인 수는 그냥 더한다. 이 때 구할 수 있는 최댓값을 더하는 문제이다.

 

간단하게 생각하면 수를 양수와 음수로 분리하여 절댓값이 큰 수 순으로 묶어서 더하면 된다. 

하지만 조심해야 할 점은 0이 포함된 수열일 수도 있다는 점과 1은 곱한 것보다 따로 더하는 게 더 크다는 점이다.

 

0이 포함될 경우 : 음수 수열의 길이가 홀수이면 큰 순으로 묶었을 때 하나가 남는다. 이를 0과 곱해서 더하면 0이 더해지므로 음수를 더하는 것보다 더 크다.

 

1이 포함될 경우 : 양수 수열 중 1과 다른 수를 곱한 것보다 따로 더하는 것이 더 크다.

 

코드는 다음과 같습니다.

n = int(input())
pos = [] # 양수 모음
neg = [] # 음수 모음
zero = 0 # 0 개수

for i in range(n):
    num = int(input())
    if num==0:
        zero += 1
    elif num > 0:
        pos.append(num)
    else:
        neg.append(num)

# 오름차순 정렬
pos = sorted(pos)
neg = sorted(neg)
res = 0

# 양수인 경우 계산 (큰 수 순으로 2개씩 곱해서 더하기)
# 1이 포함 되는 경우는 곱하는 거보다 따로 더하는 게 더 크다
for i in range(len(pos)-1, 0, -2):
    if pos[i] > 1 and pos[i-1] > 1:
        res += pos[i]*pos[i-1]
    else:
        res += pos[i]
        res += pos[i-1]

# 길이 홀수인 경우 1개 남음
if len(pos) % 2 == 1:
    res += pos[0]

# 음수인 경우 계산 (큰 음수(절댓값 큰 거) 순으로 2개씩 곱해서 더하기)
for i in range(0, len(neg)-1, 2):
    res += neg[i]*neg[i+1]

# 길이 홀수인 경우 1개 남음
# 0이 있는 경우 0과 곱해서 0을 더하도록 만드는게 더 큼
if len(neg) % 2 == 1:
    if zero != 0:
        res += 0
    else:
        res += neg[-1]

print(res)