BaekJoon1744_수 묶기

문제

풀이

어째서 알고리즘 분류에서 이 문제가 정렬 문제로 분류가 되었는지 의문이 생기는 그런 문제였다. 풀이는 단순 무식하게 정렬 한 뒤 수를 묶는 경우의 수를 모두 코드에 작성하면 된다. 정렬보다는 그리디 문제라고 생각한다.

정답 코드

from collections import deque

n = int(input())

num = []

for _ in range(n):
    num.append(int(input()))


sort_num = deque(sorted(num, reverse=True))


answer = 0

while sort_num:
    if len(sort_num) == 1:
        answer += sort_num.popleft()
        break
    
    x = sort_num.popleft()
    if x > 1:
        y = sort_num.popleft()
        if y > 1:
            answer += x*y
        if y == 1:
            answer += (x + y)
        if y < 1:
            answer += x
            sort_num.appendleft(y)
    if x == 1:
        answer += x
    
    if x == 0:
        if len(sort_num) %2 == 1:
            y = sort_num.popleft()
            answer += x*y
        else:
            answer += x
    
    if x < 0:
        sort_num.appendleft(x)
        x = sort_num.pop()
        y = sort_num.pop()
        answer += x*y

print(answer)