[백준 - 30014번] 준영이의 사랑 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 정렬, 덱

입력

첫째 줄에 진주알의 개수 $N$이 주어진다.

둘째 줄에 각 진주알의 가치 $P_1$, $P_2$, $\cdots$, $P_N$이 공백으로 구분되어 주어진다.

입력으로 주어지는 수는 모두 정수이다.

출력

첫째 줄에 목걸이의 가치의 최댓값
$X$를 출력하라.

둘째 줄에 위의 가치가 나오기 위한 목걸이를 재배열하였을 때 각 진주알의 가치에 해당하는 $N$개의 수 $A_1$, $A_2$, $\cdots$, $A_N$를 공백으로 구분하여 출력하라.

제한

• $3 \leq N \leq 2\,000$ 
• $1 \leq P_{i} \leq 1\,000$ $(1 \leq i \leq N)$ 

풀이

진주알을 재배열해서 목걸이의 가치를 최대로 만들어야 한다.

목걸이의 가치는 인접한 진주알 쌍에 대해 두 진주알의 가치를 곱한 값의 합이다.

곱은 큰 값끼리 했을 때 그 합을 최대로 할 수 있기 때문에 다음과 같이 배열할 수 있다.
5 4 3 2 1 -> 2 4 5 3 1

일반화하면 다음과 같다.
...(두 번째로 큰 값) (첫 번째로 큰 값) (세 번재로 큰 값)...

여기서 조금 걸리는건 원형이기 때문에 마지막과 첫 번째가 연결된다는 것이다.

그래도 풀이가 달라질건 없다. 어차피 큰 값은 큰 값끼리 곱하는게 최선이기 때문이다.

예를 들어 $A_N$ $A_1$를 최대화한다고 해도 5 3 1 2 4로 2 4 5 3 1과 다르지 않다.
핵심은 큰 값 큰 값이다.

그리디 + 정렬 + 덱 풀이의 시간 복잡도는 O(N*logN)이다.

$A_i$는 양의 정수인데, 나는 좀 더 문제를 심화해서 음의 정수도 있다고 가정하고 풀었다.
(물론 이게 정확한지는 모르겠지만)

만약 음수가 포함된 경우도 다르진 않다.

... (두 번째로 작은 값) (첫 번째로 작은 값) (세 번째로 작은 값)...으로 배열해야 한다.
ex) -3 -5 -2

작은 값인 이유는 음수간의 곱이기 때문에 양수가 되기 때문이다.

하지만 양과 음의 배열을 연결할 때는 음수의 가치가 나오게 된다.

그래서 앞의 연결할지 뒤에 연결할지를 비교해서 연결해야 한다.

비교해야 하는 이유는

양에서 첫 번째로 작은 값 음에서 첫 번째로 큰 값 + 양에서 두 번째로 작은 값 음에서 두 번째로 큰 값

양에서 첫 번째로 작은 값 음에서 두 번째로 큰 값 + 양에서 두 번째로 작은 값 음에서 첫 번째로 큰 값

이 두 가지 경우는 계산해 보지 않으면 모르기 때문이다. 그래서 반드시 비교 후에 가치가 더 큰 쪽으로 연결해야 한다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      ArrayList<Integer> pList = new ArrayList<>();
      ArrayList<Integer> nList = new ArrayList<>();
      for(int i=0; i<N; i++) {
          int v = Integer.parseInt(st.nextToken());
          if(0 <= v) {
              pList.add(v);
          } else {
              nList.add(v);
          }
      }
      Collections.sort(pList, Collections.reverseOrder());
      Collections.sort(nList);
      
      Deque<Integer> pDeque = new ArrayDeque<>();
      Deque<Integer> nDeque = new ArrayDeque<>();
      
      for(int i=0; i<pList.size(); i++) {
          if(i % 2 == 0) {
              pDeque.addLast(pList.get(i));
          } else {
              pDeque.addFirst(pList.get(i));
          }
      }
      
      for(int i=0; i<nList.size(); i++) {
          if(i % 2 == 0) {
              nDeque.addLast(nList.get(i));
          } else {
              nDeque.addFirst(nList.get(i));
          }
      }
      
      if(!nDeque.isEmpty()) {
          boolean back = false;
          if(nDeque.peekLast() * pDeque.peekFirst() + nDeque.peekFirst() * pDeque.peekLast() <= nDeque.peekFirst() * pDeque.peekLast() + nDeque.peekLast() * pDeque.peekFirst()) {
              back = true;
          }
          
          while(!nDeque.isEmpty()) {
              if(back) {
                  pDeque.addLast(nDeque.pollFirst());
              } else {
                  pDeque.addFirst(nDeque.pollLast());
              }
          }
      }
    
      int[] arr = new int[N];
      for(int i=0; i<N; i++) {
          arr[i] = pDeque.pollFirst();
      }
      StringBuilder sb = new StringBuilder();
      int answer = 0;
      for(int i=0; i<N; i++) {
          sb.append(arr[i]).append(" ");
          if(i == N - 1) {
            answer += arr[i] * arr[0];
            break;  
          }
          answer += arr[i] * arr[i + 1];
      }
      System.out.println(answer);
      System.out.println(sb.toString().trim());
  }
}