백준(1744) - 수 묶기 Python

백준(1744) - 수 묶기

문제풀이 : 그리디 알고리즘, 파이썬

해결방법

음수끼리인 경우는 곱한값이 크고, 양수끼리는 큰수부터 곱한값으로 구하면 된다고 단순하게 생각했었다.

하지만 0과 1에 대해서도 생각을 해줘야 해결이 가능한 문제였다.

• 1은 더한다.
• 0을 포함한 음수는 작은 수부터 곱한다
• 1을 제외한 양수는 큰 수부터 곱해야한다.

n = int(input())

arr = []
for _ in range(n):
    arr.append(int(input()))
arr.sort()
positive = [] # 양수를 담을 리스트
negative = [] # 음수를 담을 리스트
res = 0

for a in arr:
    if a <= 0:
        negative.append(a)
    elif a == 1: # 1인 경우는 결과값에 바로 더해준다.
        res += a
    else:
        positive.append(a)

for i in range(len(positive)-1, -1, -2): # 양수인 경우 뒤에서부터 계산
    if i - 1 < 0:
        res += positive[0]
    else:
        res += (positive[i] * positive[i-1])

for i in range(0, len(negative), 2): # 음수인 경우 작은 수부터 계산
    if i + 1 >= len(negative):
        res += negative[i]
    else:
        res += (negative[i] * negative[i+1])

print(res)