문제

BOJ 1744: 수 묶기 https://www.acmicpc.net/problem/1744

풀이

조건

• 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶는다.
• 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다.
• 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다.
• 수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
• 그 합이 최대가 되게 한다.

풀이 순서

• 음수와 양수를 나눠서 생각한다.
• 1은 곱할 때 보다 그냥 더할 때 가장 큰 수가 된다.
• 양수는 큰 값 부터 2개씩 곱해서 더해준다.
• 음수는 작은 값(절댓값이 큰 값)부터 2개씩 곱해서 더해준다.
  • 내림차순으로 정렬하면 편하다.
• 0은 음수와 묶어 곱하면 가장 큰 수가 된다.

코드

N = int(input())

posi = [] # 양수를 담을 배열
nega = [] # 음수를 담을 배열
answer = 0 # 출력할 정답
for _ in range(N):
  n = int(input())
  
  if n > 1:
    posi.append(n)
  elif n == 1:
    answer += 1 # 1은 곱하는 것 보다 더하는 것이 더 큰 값이 된다.
  else:
    nega.append(n)

nega.sort() 
posi.sort(reverse=True) # 양수는 내림차순으로 정렬해야 곱하는 데 편하다

# 음수의 수가 짝수일 때
if len(nega) % 2 == 0: 
    result = 0
    # 2개씩 곱해서 더해준다.
    for i in range(0, len(nega), 2):
        result += nega[i] * nega[i + 1]
    answer += result
# 음수의 수가 홀수일 때
else: 
    result = 0
    # 2개씩 곱해서 더해주고
    for i in range(0, len(nega)-1, 2):
        result += nega[i] * nega[i + 1]
    # 마지막 수는 절댓값이 가장 작은 음수이므로 그냥 더해준다.
    result += nega[-1]
    answer += result

# 양수의 수가 짝수일 때
if len(posi) % 2 == 0:
    result = 0
    # 2개씩 곱해서 더해준다.
    for i in range(0, len(posi), 2):
        result += posi[i] * posi[i + 1]
    answer += result
# 양수의 수가 홀수일 때
else:
    result = 0
    # 2개씩 곱해서 더해주고
    for i in range(0, len(posi)-1, 2):
        result += posi[i] * posi[i + 1]
    # 마지막 수는 더해준다.
    result += posi[-1]
    answer += result

print(answer)

정리

• 조건에 맞춰 여러 케이스를 생각한 뒤 해결했다.