[백준] 1744 "수 묶기" -python

 

알고리즘

 무작위로 나열된 수열로 해결하기에는 답이 없다고 판단하여 정렬한 상태에서 규칙을 찾았다. 오름차순 정렬 이후 음수와 양수가 나뉘는 부분을 생각해보았고 음수가 짝수개인 동안은 왼쪽부터 2개씩 묶고(덱에서 왼쪽 2개씩 뺌), 오른쪽에서는 1보다 큰 수가 짝수개인 동안은 2개씩 묶는다(덱에서 오른쪽 2개씩 뺌), 길이가 2이상인 경우까지 위 과정을 반복한다. 주의할 점은 왼쪽, 오른쪽 둘 다 홀수개가 남았다면 브레이크를 통해 반복을 빠져나온다. 그 다음 덱에 남은 개수에 대해 음수, 0이 같이 있으면 둘을 곱해주는 예외처리를 한 뒤에 나머지 상황은 전부 더해주면 최대가 된다.

 

소스코드

# 수 묶기
import collections
n = int(input())

arr = []
for _ in range(n):
    v = int(input())    
    arr.append(v)

arr.sort()
deque = collections.deque(arr)
result = 0
while len(deque)>1:
    if deque[0] < 0 and deque[1] < 0:
        result += deque.popleft() * deque.popleft()
    elif deque[-1] > 1 and deque[-2] > 1:
        result += deque.pop() * deque.pop()
    else:
        break
        
if len(deque) > 1:
    if deque[0] < 0 and deque[1] == 0: # 음수, 0 이 남은 경우
        deque.popleft()
        deque.popleft() # 곱해서 0 이 되므로 결과에 영향x

result += sum(deque) # 남은애들 다 더하기
print(result)

 

느낀점

 나머지 반례는 다 생각했는데 양수가 짝수개일 때 하나라도 1이면 곱해져서 같은수가 나오게 된다. 그래서 이는 최댓값이 아니고 1이 하나라도 있는 경우 더하는게 더 이득이므로 양수가 아닌 1보다 큰 양수를 조건으로 지정해야한다. 수학적으로 당연한 이야기지만 코딩을 할 때 망각해버렸다...ㅠㅠ