[백준 1744] 수 묶기 - Python

문제 보기

 

[사용한 알고리즘]

정렬, 그리디

 

[문제 접근]

양수 가장 큰 수 두 개, 음수 절댓값 가장 큰 수 두 개씩 묶는 것이 최종 합을 최대로 나오게 할 수 있다고 생각하였다. 추가적으로 1은 묶지 않는 것이 좋고, 0의 경우 음수 1개가 남은 상황에서는 묶는 것이 좋다고 생각하였다.

 

[알고리즘]

1. 입력받은 숫자를 오름차순 정렬한다.

2. 1보다 큰 수를 따로 저장한다.

3. 0 이하의 수를 따로 저장한다.

4. 2, 3의 과정에서 따로 구한 수를 2개씩 묶고 곱한다. 묶이지 않는 숫자는 그대로 더한다.

5. 2, 3 과정에서 묶이지 않은 숫자를 더해서 최종 합을 출력한다.

 

[코드]

from collections import deque


if __name__ == "__main__":
    n = int(input())
    array = [int(input()) for _ in range(n)]

    # 오름차순 정렬
    array.sort()
    q = deque(array)

    # 1보다 큰 양수 저장
    positive = []
    while q:
        num = q.pop()
        if num > 1:
            positive.append(num)
        else:
            q.append(num)
            break

    # 0이하 수 저장
    negative = []
    while q:
        num = q.popleft()
        if num <= 0:
            negative.append(num)
        else:
            q.insert(0, num)
            break

    answer = 0
    # negative 2개씩 묶어서 더하기
    for i in range(0, len(negative), 2):
        if i + 1 < len(negative):
            answer += negative[i] * negative[i + 1]
        else:
            answer += negative[i]

    # positive 2개씩 묶어서 더하기
    for i in range(0, len(positive), 2):
        if i + 1 < len(positive):
            answer += positive[i] * positive[i + 1]
        else:
            answer += positive[i]

    # 남은 수 그냥 더하기
    while q:
        num = q.pop()
        answer += num

    print(answer)