[Python 3] BOJ - 1744 "수 묶기"

 # 문제 링크 : https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 # 풀이 :

 개인적으로 이 문제의 핵심은 0, 1의 처리라고 생각한다. 만일, 0, 1이 쿼리 내에 들어오지 않는다면 음수와 양수의 두 리스트로 나누어 음수는 오름차순으로, 양수는 내림차순으로 정렬 후 짝수개 씩 묶어준 후 곱한다. 이후 쌍으로 묶이지 않는 음수와 양수를 모두 더해주면 된다. 그런데 0, 1이 쿼리 내에 들어오지 않는다는 가정이 없기 때문에, 각각의 경우에 대하여 고려해야 한다.

<그림 1>

 만일 그림 1처럼 수의 쌍들을 묶게 된다면 얻을 수 있는 값은 7이다. 그러나, 최적해는 어떠한 수도 묶지 않는 것이다. 따라서 최적해는 9이다. 왜냐하면 1은 곱셈을 하는 결과가 자기자신이기 때문에, 1은 항상 곱하는 것이 아니라 더해줘야 한다.

<그림 2>

 만일 그림 2처럼 수의 쌍을 묶게 된다면 얻을 수 있는 값은 60이다. 그러나, 최적해는 -8과 -7, -1과 0을 묶는 것이다. 왜냐하면 0은 어떤 수와 묶는다 하더라도 0이 되기 때문에 쌍을 이루지 못하는 음수를 묶으면 수들의 합의 최댓값을 구할 수 있다. 따라서 음수를 담고 있는 리스트에서 한 쌍을 뽑고 쌍을 이루지 못하는 음수들이 있고 0이 존재한다면 0과 나머지 음수를 묶는다. 그래도 남는 음수들은 어쩔 수 없이 더해줘야 한다

 이후 짝수도 같은 과정을 거치되, 쌍을 이루지 않는 짝수는 굳이 0과 묶어줄 필요가 없으므로 그대로 더한다. 마지막으로 1은 묶지 않는 것이 이득이므로 1의 갯수만큼 더해주면 정답을 구할 수 있다.

 

import sys

# 입력부
n = int(sys.stdin.readline())

# neg : 음수 리스트
# pos : 1 제외 양수 리스트
# zero : 0 리스트
# one : 1 리스트
neg = []
pos = []
zero = []
one = []

# 각 숫자를 경우에 따라 다른 리스트에 담는다
for i in range(n):
    n = int(sys.stdin.readline())
    if n < 0:
        neg.append(n)
    elif n > 1:
        pos.append(n)
    elif n == 1:
        one.append(n)
    else:
        zero.append(n)
        
# 음수는 내림차순 (절댓값이 큰 수가 앞에), 양수는 오름차순으로 정렬한다
neg.sort(reverse=True)
pos.sort()

# ans : 정답 배열
ans = []

# 음수 리스트에서 쌍을 추출후, 정답배열에 곱한 값을 넣는다
while len(neg) >= 2:
    ans.append(neg.pop() * neg.pop())
    
# 남은 음수에 대해
while neg:
	# 0 리스트가 비지 않았다면 0과 나머지 음수를 묶어준다
    if zero:
        zero.pop()
        neg.pop()
    # 0 리스트가 비었다면 나머지 음수를 정답 배열에 추가한다
    else:
        ans.append(neg.pop())
        
# 양수 배열도 마찬가지로 한 쌍으로 묶은 값을 정답배열에 저장하고 남은 양수도 정답 배열에
# 그대로 저장한다
while len(pos) >= 2:
    ans.append(pos.pop() * pos.pop())
while pos:
    ans.append(pos.pop())
    
# 마지막으로 1을 정답 배열에 추가한다
while pone:
    ans.append(one.pop())
    
# 정답 출력
print(sum(ans))