[백준] 수열의 점수 / Python / 골드 4

🚩문제 주소

📄풀이

그리디

0 이하의 정수를 음수, 1인 수, 나머지 양수로 나눕니다.

양수들은 큰 수 부터 올 수 있게 내림차순, 음수들은 작은 수부터 올 수 있게 오름차순으로 정렬합니다.(음수들은 작은 두 개의 수 끼리 곱해야 커지므로)

각 배열의 길이가 짝수이면 2개 씩 짝지어서 곱한 뒤 정답에 저장합니다.
각 홀수이면 마지막 수를 제거한 뒤 정답에 저장하고 나머지를 짝지어서 곱한 뒤 저장합니다.
길이가 홀수일 경우 배열의 마지막 수는 최댓값에 가장 영향을 작게 주는 수이기 때문입니다.

마지막으로 따로 모은 1들을 전부 더한 뒤에 정답을 출력합니다.

👨‍💻코드

n = int(input())
positive = [] # 양수
negative = [] # 음수
one = [] # 1만 모으기
answer = 0 # 정답
for _ in range(n):
  temp = int(input())
  if temp == 1:
    one.append(temp)
  elif temp <= 0:
    negative.append(temp)
  else:
    positive.append(temp)
positive.sort(reverse=True) # 큰 수 부터 올 수 있게 내림차순
negative.sort() # 작은 수 부터 올 수 있게 오름차순

# 배열의 길이가 짝수이면 2개 씩 짝지어서 곱한 뒤 정답에 저장
# 홀수이면 마지막 수를 제거한 뒤 정답에 저장하고 나머지를 짝지어서 곱한 뒤 저장
if len(positive)%2==0:
  for i in range(0, len(positive), 2):
    answer += positive[i]*positive[i+1]
else:
  answer += positive.pop()
  for i in range(0, len(positive), 2):
    answer += positive[i]*positive[i+1]

if len(negative)%2==0:
  for i in range(0, len(negative), 2):
    answer += negative[i]*negative[i+1]
else:
  answer += negative.pop()
  for i in range(0, len(negative), 2):
    answer += negative[i]*negative[i+1]

# 모은 1들을 전부 더하기 -> 1은 곱하는 것 보다 더하는 게 더 큼
answer += sum(one)

print(answer)