[Python] 2036번 수열의 점수 / 1744번 수 묶기

 

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

2036번: 수열의 점수

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

1744번: 수 묶기

---

 

22/11/20 / 22/11/23

 

 

두 문제는 $N$의 크기만 다르고 솔루션이 완전히 동일한 문제로, 사실 $N$의 크기도 그렇게 크게 중요하지 않은 요인인 것 같아서 같이 올려본다.

 

그리디 문제인데 약간의 예외처리를 해줘야 되는 부분이 필요한 문제로, 자료 구조 중에서 덱을 이용하여 구현한다면 많은 조건분기 없이 쉽게 해결할 수 있는 문제이다. (실제 문제에서는 많은 조건 분기 태그가 달려있다)

---

 

문제 접근 방식:

 

 

두 문제는 거의 같은 문제이기 때문에 2036번을 기준으로 설명하겠다.

 

문제를 보고, 그리디적인 접근 방식을 해야겠다고 생각한 이유는 다음과 같다.

 

먼저 문제를 보고 바로 생각한 점은 "정수 수열에서 음수가 있으면 음수가 안나오도록 하는 것이 항상 이득"이란 점이었다. 

 

이 생각을 한 순간, 어떤 특정한 행동을 하면 항상 이득이 나온다는 점에서 "이 문제는 그리디적인 접근을 해야겠구나"라고 느꼈다.

 

 

실제로, 만약 주어진 수열에서 음수가 존재한다면, 그 음수는 무조건 음수랑 곱해야 이득이라는 사실을 우리는 알 수 있다.

 

마찬가지 이유로, (음수)*(양수)는 손해가 된다는 사실을 알고 있기 때문에 양수도 되도록이면 양수끼리 곱해야 된다는 사실을 알 수 있다.

 

 

그리고, 절댓값이 큰 애들끼리 곱하는 것이 더욱 이득이라는 사실을 알 수 있다.

 

이는 예제를 통해서 추론을 한 것인데, 실제로 그렇게 되는지에 대한 간단한 증명은 아래와 같다.

 

증명)
만약 $a$, $b$, $c$, $d$가 있고, $a \leq b \leq c \leq d \leq 0$가 성립한다고 해보자.
그렇다면, $a$가 절댓값이 제일 크고, $d$가 절댓값이 제일 작다.
절댓값이 큰 두개끼리 곱해서 더한 $ab + cd$와, 절댓값이 작은애와 큰 애끼리 곱해서 더한 $ad + bc$를 비교해보자.
$ab + cd$ $-$ $ad - bc$ $=$ $a(b-d) + c(d-b)$ $=$ $(음)*(음) + (음)*(양)$인데, $a$의 절댓값이 $c$보다 크므로, 이 식은 $0$보다 크다. 따라서 절댓값이 큰 애들끼리 묶은 $ab+cd$가 더 이득이다.

 

이 두 가지 사실을 조합하면, 음수는 되도록 음수끼리 곱하고, 양수도 양수끼리 곱하는데, 절댓값이 큰 애들끼리 곱해야 된다는 결론이 나오게 된다.

 

한 가지 주의해야될 점은 $0$과 $1$의 존재이다.

 

$1$은 음수든 양수든 간에 어떤 숫자와 곱하면 그 숫자가 그대로 나오기 때문에 곱하는 것보다는 따로따로 더하는 것이 이득이다.

 

$0$은 양수를 곱한다면 $0$이 나오기 때문에 무조건 손해이고, $0$에 음수를 곱하거나 그냥 따로 더하는 것이 이득이다.

 

 

이 사실을 종합해 보자면, 다음과 같은 결론을 얻을 수 있다.

 

정렬을 한 뒤, 음수는 왼쪽부터 있으므로, 왼쪽부터 두 개씩 묶어서 계속 더해준다. 이때, $0$은 음수와 곱하는 것이 이득이므로, 음수에 $0$이 포함되어있다고 생각해도 된다.

 

이후 더이상 곱할 음수가 없다면 멈춘다.

 

절댓값이 큰 양수는 오른쪽부터 있으므로, 오른쪽부터 두 개씩 묶어서 계속 더해준다. 이때, $1$은 양수랑 곱하는 것이 손해이기 때문에 두 개씩 묶은 숫자 중에 $1$이 있다면 멈추고 그때부터는 그냥 따로 더해준다.

 

이후 남은 리스트에는 $0$과 $1$밖에 남지 않는데, 이 리스트는 그냥 계속 따로 더해주면 끝이다.

 

 

나는 이를 구현하기 위해 다음과 같은 방법을 취했다.

 

먼저, 숫자 리스트를 입력받으면 이를 정렬한다.

 

이를 "덱"에 넣으면, 오른쪽과 왼쪽에서 빼는 것이 수월할 것이라고 생각되어, 숫자 리스트를 덱으로 바꿔주었다.

 

이후 음수 처리 과정에서는 덱의 왼쪽에서 원소를 뺐고, 양수 처리 과정에서는 덱의 오른쪽에서 원소를 뺐으며, 이후 $0$과 $1$만 남았을 때에는 그냥 하나씩 빼서 더해주었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2036번 수열의 점수
# 그리디, 정렬, 자료구조, 덱
'''
접근 방법:
음수는 무조건 음수랑 곱해야 이득
이유)
1.수열에서 음수가 만약에 짝수 개 있다고 해보자.
그러면 무조건 음수끼리 짝지어서 양수로 만들어서 점수로 만드는게 이득임.
같은 상태에서 하나는 두 음수를 각각 총점에 더한거랑
하나는 두 음수를 짝지어서 곱해서 총점에 더한거랑
전자는 음수를 더하는거고 후자는 어쨌든간에 양수를 더한 거기 때문.

-절댓값이 큰 애들끼리 차례로 곱해야 이득임
이유)
예를 들어 a, b, c, d가 있고, a <= b <= c <= d < 0라고 하자.
그러면 a가 절댓값이 제일 크고 d가 제일 작다.
그러면 ab + cd 와 ad + bc의 크기를 비교하면
ab + cd - ad - bc = a(b-d) + c(d-b) = (음)*(음) + (음)*(양) 인데, a의 절댓값이
c보다 크므로, 이식은 0보다 큼.
따라서 절댓값이 큰 애들끼리 묶은 ab+cd가 더 이득임.

-위의 두개를 종합하면,
음수가 짝수개 있으면, 음수끼리 절댓값 큰 순서대로 곱해야됨.
만약 음수가 홀수개 있으면? 어쨌든 음수 하나를 남길 수 밖에 없음
그러면 절댓값이 작은 애를 남기는게 이득임.

양수의 경우는 어떨까?
0과 1을 제외한다면, 절댓값이 큰 애들끼리 차례로 곱하는게 이득인건 음수랑 똑같음.
만약 곱해야되는 수가 0이나 1이면 그냥 따로따로 하는게 이득임

그러면 경우의 수를 나눠보자.
1. 음수가 짝수개인 경우
음수가 짝수개면 무지성으로 두개씩 묶으면 됨
2. 음수가 홀수개인 경우
2-1. 양수리스트의 마지막 원소가 0이라면
0번째 원소를 가져와서 음수에다 곱해줌으로써 상쇄시키자.
2-2. 양수리스트의 마지막 원소가 0이 아니라면
그냥 음수리스트 마지막 원소는 단독으로 더하자.
'''
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
num_li = deque(sorted(int(input()) for _ in range(N)))
total = 0
# 음수 처리 과정
while num_li:
    a = num_li.popleft()
    if a >= 1:  # 이제 다 뽑고 양수만 남은 경우
        num_li.appendleft(a)
        break
    if not num_li:
        total += a
        break
    b = num_li.popleft()
    if b >= 1: # 이제 다 뽑고 양수만 남은 경우
        total += a
        num_li.appendleft(b)
        break
    total += a*b
# 양수 처리 과정
while num_li:
    a = num_li.pop()
    if a == 1 or a == 0:
        num_li.append(a)
        break
    if not num_li:
        total += a
        break
    b = num_li.pop()
    if b == 1 or b == 0:
        total += a
        num_li.append(b)
        break
    total += a*b
# 0과 1 처리 과정
while num_li:
    a = num_li.pop()
    total += a
print(total)