[백준/30014] 준영이의 사랑 (Python)

Problem : https://www.acmicpc.net/problem/30014

30014번: 준영이의 사랑

 

Difficulty : Gold 2

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 N개의 진주로 이루어진 원형의 진주 목걸이를 선물해 줄 생각이다.

i(1 <= i <= N)번째 진주알은 가치 Pi를 지닌다. 이 진주알 N개를 적당한 순서로 재배열하여 목걸이의 가치가 최대가 되는 목걸이를 선물하려고 한다. 이때 임의로 재배열한 후 i번째 진주알의 가치를 Ai(1 <= i <= N)라 하자. 목걸이의 가치 X는 서로 인접한 진주알 쌍에 대해 두 진주알의 가치를 곱한 값의 합이다.

수식으로 표현하면 다음과 같다. X = A1A2 + A2A3 + ... ANA1 

목걸이의 가치 X의 최댓값과 그 가치가 나오기 위해 목걸이를 재배열했을 때 i번째 진주알의 가치 Ai를 출력하라. 가치가 최대인 목걸이 배치가 여러 가지 존재할 경우, 그 중 하나를 아무거나 출력한다.

 

입력 및 출력

 

입력

 

첫째 줄에 진주알의 개수 N이 주어진다. 둘째 줄에 각 진주알의 가치 P1, P2, ... PN이 공백으로 구분되어 주어진다.
입력으로 주어지는 수는 모두 정수이다.

 

출력

 

첫째 줄에 목걸이의 가치의 최댓값 X를 출력하라.
둘째 줄에 위의 가치가 나오기 위한 목걸이를 재배열하였을 때 각 진주알의 가치에 해당하는 N개의 수 A1, A2, ..., AN를 공백으로 구분하여 출력하라.

 

입력 예시

 

3
2 3 5

 

출력 예시

 

31
2 3 5

 

 

---

 

풀이

 

곱셈을 개략적으로 생각해보면, 큰 수끼리의 곱이 제일 가치의 크기를 높인다는 사실을 직관적으로 알 수 있다. 즉 가장 큰 가치를 중심으로, 양쪽으로 번갈아가며 가치가 높은 진주를 끼워나가는 경우를 생각해 볼 수 있다. 덱을 활용해 정렬된 리스트의 원소를 앞뒤로 삽입해보자.

 

풀이 코드

from collections import deque

N = int(input())
pearls = sorted(map(int, input().split()), reverse = True)
lst = deque()
for i in range(N) :
  if i % 2 :
    lst.append(pearls[i])
  else :
    lst.appendleft(pearls[i])

ans = 0
for i in range(N) :
  ans += lst[i] * lst[(i+1)%N]
print(ans)
print(*lst)

풀이 완료!