[백준] 1744번 수 묶기

문제

{0, 1, 2, 3, 4, 5}와 같은 수열이 주어질 때 규칙에 따라 최대의 값을 구해라.
두 개의 수를 묶어 곱한 뒤에 더할 수 있다.
ex) 0 + 1 + (2*3) + (4*5) = 27처럼 묶었을 때 최대의 합을 얻을 수 있다.
수열의 크기는 N. (단, N은 50보다 작은 자연수)
N의 원소의 범위는 -1000 ~ 1000이다.

풀이

필자가 생각한 규칙은 다음과 같다.

1. 양수의 경우 큰 수부터 2개씩 묶어준다. (1은 제외, 1은 더해줘야 크다)
2. 음수의 경우 홀수개 짝수개일 때로 나눈다.
   • 짝수개일 때 -> 작은 수부터 2개씩 묶어준다.
   • 홀수개일 때는 짝수개와 유사하지만 0의 존재 유무에 따라 나눈다.
     • 유 -> 남은 1개를 0과 묶는다.
     • 무 -> 남은 1개를 더한다

자세한건 코드에서 다루겠다.

전체코드

import sys
input = sys.stdin.readline

# 0 ~ 999       -> -1000 ~ -1
# 1000          -> 0
# 1001 ~ 2000   -> 1 ~ 1000
numList = [0 for _ in range(-1000, 1001)]
n = int(input())
answer = 0

for _ in range(n):
    num = int(input())
    numList[num + 1000] += 1

# 음수일때 (-1000 ~ -1) 인덱스는 (0 ~ 999)
# 2개씩 짝지어 answer에 더해줌
# 홀수개였다면 prevNum에 0이 아닌 값이 담겨나옴
i = 0
prevNum = 0
while i < 1000:
    cnt  = numList[i]

    while cnt > 0:
        if prevNum != 0:
            answer += prevNum * (i - 1000)
            prevNum = 0
        else:
            prevNum = i - 1000

        cnt -= 1

    i += 1

# 음수가 홀수개인데 0이 없다면 그대로 더해줌
# 0이 있다면 0이랑 곱해서 0을 만들어주니 아무일도 일어나지 않음
if prevNum != 0 and not numList[1000]:
    answer += prevNum

# 양수일때 (2 ~ 1000) 인덱스는 (1002 ~ 2000)
# 1일 때는 곱하는게 아닌 더해주어야 최대값
# 뒤에서부터 2개씩 짝지어 answer에 더해줌
i = 2000
prevNum = 0
while i > 1001:
    cnt  = numList[i]

    while cnt > 0:
        if prevNum != 0:
            answer += prevNum * (i - 1000)
            prevNum = 0
        else:
            prevNum = i - 1000

        cnt -= 1

    i -= 1

# 양수가 짝수개였으면 0이 더해짐
# 양수가 홀수개였으면 외톨이가 더해짐
answer += prevNum

# 1은 더해줌
answer += numList[1001]
print(answer)