1744 수 묶기

 

합이 최대가 하기 위해서는 양수는 양수끼리, 음수/0은 음수/0끼리 곱하고 1은 더해야 한다.

양수는 큰 수 끼리, 음수는 절댓값이 큰 수 끼리 곱해야 보다 큰 수를 만들 수 있으므로 우선순위 큐를 통해 답을 도출할 수 있다.

 

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

public class Main {
    
    static int n, answer;
    static PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
    static PriorityQueue<Integer> zeroAndMinusPq = new PriorityQueue<>();
    
    public static void main (String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for (int i=0;i<n;i++) {
            int num = Integer.parseInt(br.readLine());
            if (num == 1) answer += 1;
            if (num > 1) plusPq.offer(num);
            if (num < 1) zeroAndMinusPq.offer(num);
        }
        
        while (plusPq.size() > 1) {
            answer += plusPq.poll() * plusPq.poll();
        }
        if (plusPq.size() == 1) answer += plusPq.poll();
        
        while (zeroAndMinusPq.size() > 1) {
            answer += zeroAndMinusPq.poll() * zeroAndMinusPq.poll(); 
        }
        if (zeroAndMinusPq.size() == 1) answer += zeroAndMinusPq.poll();
        
        System.out.println(answer);
    }
}

 

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