1. 문제

---

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(23)+(45) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

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

2. 아이디어

---

• mine(fail)
  수의 합이 최대가 되려면 오름차순 정렬 후 계산한다.
  틀렸습니다.

  1. 수를 입력받고 오름차순 정렬한다.
  2. 현재 수가 1 이하면 더한 후 다음 수를 가져온다.
  3. 그게 아닐 경우, 다음 수와 곱한 값을 더한 후 다다음 수를 가져온다.

• mine(code), copy(hint)
  개선 : 음수 처리, 0과 1 처리.

  1. minus : 음수와 0
  2. plus : 2 이상 양수
  3. 입력받은 수에서 1은 result에 더해주고 minus와 plus는 append
  4. minus, plus 오름차순으로 sort
  5. minus가 한 개일 경우 : result에 +
  6. minus가 짝수일 경우 : 짝지어서 곱한 후 result에 +
  7. minus가 홀수일 경우 : 작은 수 부터 짝지어서 곱한 후 result에 + 한 후 가장 큰 마지막 수 result +
     plus일 경우 minus와 홀수일 경우만 다름 : 가장 작은 첫 번째 수를 result에 + 한 후 나머지는 짝지어서 곱한 후 result에 +

힌트 출처 : https://m.blog.naver.com/PostView.naver?blogId=pjok1122&logNo=221652191176&proxyReferer=https:%2F%2Fwww.google.com%2F

3. 코드

---

mine(fail)

n = int(input())
k = []
for i in range(n):
  k.append(int(input()))
k.sort()
k.append(0)
result = 0
index = 0

while index < n:
  if k[index] <= 1:
    result += k[index]
    index += 1
  else:
    result += k[index] * k[index + 1]
    index += 2

print(result)

mine(code), copy(hint)**

import sys

input = lambda: sys.stdin.readline()
n = int(input())
result = 0
minus = []
plus = []

for i in range(n):
  temp = (int(input()))
  if temp <= 0:
    minus.append(temp)
  elif temp > 1:
    plus.append(temp)
  else:
    result += temp

minus.sort()
plus.sort()

if len(plus)%2 == 0:
  for i in range(0, len(plus), 2):
    result += plus[i] * plus[i+1]
elif len(plus) == 1:
    result += plus[0]
else:
  for i in range(1, len(plus), 2):
    result += plus[i] * plus[i+1]
  result += plus[0]

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

print(result)