[백준] 수 묶기(1744) - python

✏️ 문제

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(23)+(45) = 27이 되어 최대가 된다.
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

🎈 입력

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

🎈 출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

🎈 입출력 예

<입력>
4
-1
2
1
3

<출력>
6

<입력>
6
0
1
2
4
3
5

<출력>
27

<입력>
1
-1

<출력>
-1

<입력>
3
-1
0
1

<출력>
1

<입력>
2
1
1

<출력>
2

👩‍💻 내 코드

이 문제는 어려워 보일 수 있지만 조금만 생각해보면 쉽게 풀 수 있는 문제였다. 양수와 음수, 0을 나누었을 때 음수를 중요하게 생각하고 풀었다. 음수 경우의 수를 살펴보면 아래와 같다.

1. 음수가 1개 존재할 때 : 0이 존재하면 0을 곱해서 제거
2. 음수가 여러개 존재할 때 : 음수끼리 곱해서 더함

양수의 경우, 1이 존재할 때만 생각해주면 된다. 1이 있을 경우 곱하는 것 보다 더하는 것이 더 큰 수가 되기 때문이다.

1이 존재할 경우 곱하지 않고 바로 더한다.

위의 경우의 수를 생각하고 아래와 같이 구현했다. (코드 더러움 주의...!!)

N = int(input())

positive = [] # 양수
negative = [] # 음수
zero = 0 # 0의 개수

for _ in range(N):
    x = int(input())
    if x < 0:
        negative.append(x)
    elif x == 0:
        zero += 1
    else:
        positive.append(x)

positive.sort()
negative.sort(reverse=True) # 음수의 경우 배열을 뒤집어서 끝부터 꺼내서 곱해야 최대가 됨
result = 0

while negative:
    if len(negative)%2 == 0: # 2개씩 짝지을 수 있을 때
        A = negative.pop()
        B = negative.pop()
        result += A*B
    else:
        if len(negative) == 1: # 1개가 남는 경우
            if zero == 0: # 0이 없는 경우 음수를 바로 더해준다.
                result += negative.pop() 
            else: # 0이 있는 경우 0을 곱해 없애주고 0의 개수를 1개 줄인다.
                zero -= 1
            break
        else:
            A = negative.pop()
            B = negative.pop()
            result += A*B 

while positive:
    if len(positive)%2 == 0: # 2개씩 짝지을 수 있을 때
        A = positive.pop()
        B = positive.pop()
        if A == 1 or B == 1: # 1이 존재할 때
            result += (A+B) # 바로 더해준다.
        else:
            result += A*B
    else:
        if len(positive) == 1:
            result += positive.pop()
        else:
            A = positive.pop()
            B = positive.pop()
            if A == 1 or B == 1:
                result += (A+B)
            else:
                result += A*B

print(result)

지금보니까 코드가 너무 길다...ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 다른분들이 구현한 코드를 보면 더 짧게 쓸 수 있는 것 같던데 더 효율적으로 짤 수 있는 방법을 생각해 보아야겠다.