[백준알고리즘] 1744번: 수 묶기 -Python

[백준알고리즘] 1744번: 수 묶기 -Python

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

주어진 조건은 아래와 같다.

• 수열에서 임의의 두 수를 곱할 수 있다.
• 한 번 묶여서 곱해졌다면 더 이상 묶이지 못한다.
• 이때 수열의 합의 최대를 구하라.

따라서 두 수의 곱이 최대가 되게 해야 한다. 또는 덧셈이 더 낫다면 덧셈인 채로 두어야 한다.

 

간단하게 생각하면 임의의 두 수의 곱이 최대가 되려면 가장 큰 두 개의 양수를 곱하거나 가장 작은 두 개의 음수를 곱하면 될 것이다. 그렇기 때문에 우선은 음수 입력과 양수 입력을 별개로 받아서 각각 두 개씩 묶어주는 과정을 해주었다. 따로 해주는 이유는 음수와 양수를 곱하면 덧셈했을 때보다 작아지는 것이 분명하기 때문에 묶을 필요가 없기 때문이다.

 

그리고 생각해볼 것은 0이다. 0이 있는 경우와 없는 경우가 어떻게 다를 것인가를 생각해보았다. 0이 있게 되면 양수에서는 덧셈으로 처리하는 것이 이득이다. 양수와 묶게되면 나중에 더했을 때 값이 작아지기 때문이다. 하지만 음수에서는 음수 하나와 0을 묶게 되면 나중에 더했을 때 증가하게 된다. 각각 더했을 때보다 값이 커지기 때문이다.

 

지금까지 알아낸 것들을 통해서 아래와 같은 값들을 생각해볼 수 있다.

(-2, -3)  → 더할 때: -5 < 곱할 때: 6

(-2, 0)   → 더할 때: -2 < 곱할 때: 0

(2, 3)    → 더할 때: 5  < 곱할 때: 6

(0, 3)    → 더할 때: 3 > 곱할 때: 0

(-1, 3)   → 더할 때: 2  > 곱할 때: -3

(-3, 1)   → 더할 때: -2 > 곱할 때: -3

 

여기까지는 쉽게 생각할 수 있다. 추가로 고려해야할 값은 1이다. 우선 음수와 묶이는 것은 묶이지 않을 때보다 값이 작아지기 때문에 고려하지 않겠다. 1과 임의의 양수가 묶일 때를 생각해봐야한다. 당연하게도 곱했을 때보다 더했을 때 값이 커진다. 이점을 놓쳐서 첫 제출 때 틀렸다 ㅎㅎ.. 생각해놓고 코딩할 때 까먹었다.

 

import sys
 
n = int(sys.stdin.readline())
negative, positive = [], []
zero = 0
 
for i in range(n):
    m = int(sys.stdin.readline())
    if m < 0:
        negative.append(m)
    elif m == 0:
        zero += 1
    else: # m > 0
        positive.append(m)
 
nl, pl = len(negative), len(positive)\
negative.sort()
positive.sort(reverse=True)
res = []
# negative
for i in range(0, nl-1, 2):
    res.append(negative[i]*negative[i+1])
if nl % 2 == 1 and zero == 0:
    res.append(negative[nl-1])
# positive
for i in range(0, pl-1, 2):
    if positive[i] > 1 and positive[i+1] > 1:
        res.append(positive[i]*positive[i+1])
    else:
        res.extend([positive[i], positive[i+1]])
if pl % 2 == 1:
    res.append(positive[pl-1])
 
print(sum(res))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다