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

골드4 문제이며, 제한 시간은 2초이다.

문제

해결 과정

우선 묶었을 때 가장 최대가 나오려면 양수는 큰 수끼리 묶어야 하고, 음수의 경우 작은 수끼리 묶어야 큰 양수가 된다. 그리고 1은 곱하는 것보다 더하는 경우에 값이 더 커진다. 마지막으로 0은 음수가 홀수 개인 경우 음수랑은 곱하는게 더 커지고, 양수와는 묶지 않는 것이 좋다.

따라서

1. 입력 받은 값을 양수, 음수 리스트로 나누며, 0은 음수 리스트에 포함시킨다. 이 때 1은 양수에 포함시키지 않고, 결과에 바로 더해준다.
2. 양수는 내림차순, 음수는 오름차순 정렬을 해서 절댓값이 큰 수끼리 묶을 수 있도록 해준다.
3. 이렇게 정렬을 했을 경우 맨 뒤에는 가장 작은 수가 있을 것이며, 묶을 때는 두 개씩 묶으므로 음수, 양수 리스트의 길이는 짝수여야 한다.
4. 따라서 길이가 홀수인 경우 어차피 못 묶여서 더해질 것이므로 미리 더하고, 양수, 음수 리스트의 길이를 슬라이싱해서 짝수로 만든다.
5. 이제 두 개씩 묶어가며 결과에 더해준다.

n = int(input())
arr = []
for _ in range(n):
  arr.append(int(input()))
arr.sort()

natural = []
negative = []
result = 0

for i in arr:
  if i <= 0:
    negative.append(i)
  elif i > 1:
    natural.append(i)
  else:
    result += 1

natural.sort(reverse=True)

if len(negative) % 2 != 0:
  result += negative[-1]
  negative = negative[:-1]
for i in range(0, len(negative)-1, 2):
  result += negative[i] * negative[i+1]

if len(natural) % 2 != 0:
  result += natural[-1]
  natural = natural[:-1]
for i in range(0, len(natural)-1, 2):
  result += natural[i] * natural[i+1]

print(result)

정당성 분석

1. 음수끼리 곱하는 것은 음수가 짝수개인 경우 양수가 되므로 최대의 결과값을 얻을 수 있고, 0을 음수 리스트에 포함하는 이유는 양수는 0과 만나면 무조건 더하기 연산이지만, 음수는 자기보다 작은 음수와 곱해지는게 아닌 이상 0과 곱하는게 최대 값을 만들기 유리하기 때문이다
2. 1의 개수를 더해주는 이유는 1은 뭐랑 곱해도 다 자기자신이기 때문에 더해주는게 무조건 커지기 때문
3. 양수를 내림차순으로 한 이유는 큰 값부터 묶기 위해서이다.