[BOJ] 1744 수 묶기

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

수열에서 임의의 위치에 있는 두 수를 묶을 수 있는데 묶게 되면 두 수는 곱해진다. 묶는 거는 할 수도 있고 안 할 수도 있는데 이렇게 했을 때 수열의 합이 최대가 되게 하는 문제이다.

코드 1 - 25% 실패

최초에 접근을 어떻게 했는가하면 수열의 양수와 음수를 구분하고 0은 유무만 표시했다.

그리고 양수, 음수 리스트를 양수는 오름차순, 음수는 내림차순으로 정렬했다.

그러고 양수와 음수리스트 각각 수를 두 개씩 pop해서 곱한 뒤에 ans에 더해주었고, 양수 리스트에 수가 남으면 그거는 그대로 더해주고 음수 리스트에 수가 남으면 만약 0이 있으면 0을 곱해서 아니라면 그대로 더해주었다.

n = int(input())


pos = []
zero = 1
neg = []

for _ in range(n):
  t = int(input())
  
  if t > 0:
    pos.append(t)
  elif t < 0:
    neg.append(t)
  else:
    zero = 0
    

neg.sort(reverse=True)
pos.sort()

ans = 0

while len(pos) > 1:
  ans += pos.pop() * pos.pop()

if pos:
  ans += pos.pop()

while len(neg) > 1:
  ans += neg.pop() * neg.pop()

if neg:
  ans += neg.pop() * zero

print(ans)

그런데 25%에서 실패했는데 왜 실패했는지 모르겠다.

코드 2

n = int(input())


pos = []
zero = 1
neg = []

for _ in range(n):
  t = int(input())
  
  if t > 0:
    pos.append(t)
  elif t < 0:
    neg.append(t)
  else:
    zero = 0
    

neg.sort(reverse=True)
pos.sort()

ans = 0

while len(pos) > 1:
  a = pos.pop()
  b = pos.pop()
  
  if a == 1 or b == 1:
    ans += a + b
  else:
    ans += a * b

if pos:
  ans += pos.pop()

while len(neg) > 1:
  ans += neg.pop() * neg.pop()

if neg:
  ans += neg.pop() * zero

print(ans)

1일 경우에 곱하게되면 의미 없게 되는데 그거를 간과했다.
양수 리스트에서는 두 숫자를 뽑고 둘 중 하나가 1이라면 그대로 더하고 아니라면 곱해서 더하는 방식으로 수정했고 통과할 수 있었다.