수 묶기 (1744번) - 백준 (BOJ)

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

1744번: 수 묶기

 

 

백준 - 수 묶기 (1744번)

 

난이도 : Gold 4

알고리즘&자료구조 : Sorting (정렬)

풀이 소요 시간 : 20분

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    pos = []; neg = []; ones = 0
    for _ in range(int(input())):
        if (x := int(input())) <= 0:  neg.append(x)
        elif x == 1:  ones += 1
        else:  pos.append(x)
    pos.sort()
    neg.sort(reverse=True)
    pl, nl = len(pos), len(neg)
    acc = 0
    while 2 <= nl:
        acc += neg.pop() * neg.pop()
        nl -= 2
    while 2 <= pl:
        acc += pos.pop() * pos.pop()
        pl -= 2
    print(acc + (neg[0] if nl else 0) + (pos[0] if pl else 0) + ones)

 

 

① 입력으로 주어지는 숫자들을, 아래와 같이 3가지 카테고리로 분류한다.

pos (list : 1을 제외한 자연수)
neg (list: 0 이하의 정수)
ones (int: 1의 개수)

 

② pos와 neg를 각각 정렬한다.

 

③ pos 내에서 절대값이 가장 큰 두 개의 수를 곱하고, 그 값을 acc에 더한다.

이 작업을 pos의 원소가 0 또는 1개가 될 때까지 반복한다.

 

④ neg 에서도 ③ 작업을 동일하게 진행한다.

 

⑤  neg와 pos에 남은 원소가 있다면 acc에 더해주고,

마지막으로 ones 값을 acc에 더해주면, 그 값이 가능한 최댓값이다.

 

⑥ acc 를 출력한다.