[백준] 1744 : 수 묶기 - Python

문제

수 묶기
길이가 n인 수열. 그 수열의 합을 구하기
수열의 합을 구할 때 두 수를 묶을 수 있음. 두 수를 묶을 때 곱하거나 더하거나 가능.
수열의 모든 수는 단 한번만 묶거나 묶지 않아야 함.

합이 최대가 되도록 구하기

기본적으로 생각했어야 하는 것이, 0이하와 양수를 구분했어야 함.
양수와 음수를 따로 저장. 정렬.

결국 가장 큰 수를 뽑아낼 때 최적의 해를 보장한다.
하지만 양수와 음수에 대해서만 고려해줬으면 됐음

나는 우선순위 큐를 통해 문제 해결.

import heapq
import sys
sys.stdin = open("input.txt", "rt")

# 길이가 n인 수열, 그 수열의 합 구하기
# 수열의 두 수를 묶어서 곱한 후 더함
# 수열의 각 수를 적절히 묶었을 때 합이 최대
# 곱한거랑 그냥 더한거랑 뭐가 더 큰지 판단해서 이어가면 될 듯
# 정렬 : 3 2 1 -1
# 3*2 3+2 -> 3*2 채택 : 6
# 1*-1, 1-1 -> 1-1 채택 : 0
# 이미 묶은 애는 더이상 묶을 수 없음

n = int(input())
plus = [] # 양수 저장
minus = [] # 0이하 저장

for _ in range(n):
    num = int(input())
    if num > 0: heapq.heappush(plus, -num) # 양수는 내림차순
    else: heapq.heappush(minus, num) # 음수는 오름차순

temp = []
res = 0
while len(plus) > 1:
    numA = -heapq.heappop(plus)
    numB = -heapq.heappop(plus)
    if numA * numB > numA + numB:
        res += numA * numB
    else:
        res += numA + numB
if plus:
    temp.append(-heapq.heappop(plus))

while len(minus) > 1:
    numA = heapq.heappop(minus)
    numB = heapq.heappop(minus)
    if numA * numB > numA + numB:
        res += numA * numB
    else:
        res += numA + numB
if minus:
    temp.append(heapq.heappop(minus))
while len(temp) > 1:
    numA = heapq.heappop(temp)
    numB = heapq.heappop(temp)
    if numA * numB > numA + numB:
        res += numA * numB
    else:
        res += numA + numB
if temp:
    res += heapq.heappop(temp)
print(res)

코멘트.

한 턴에 deque이든 pq든 2번 뽑아내야 하는 경우 while문에서의 조건문은 len(pq) > 1 를 고려하자.

이렇게 조건을 걸면 1개가 남은 경우만 따로 처리해주면 되고 코드도 간편해진다.