[Java] 백준_수 묶기_1744

문제

풀이

수열이 주어졌을 때 두 수를 묶거나 또는 묶지 않아서 최댓값을 구해야 한다. 기본적으로 우리가 알고 있는 지식을 이용해서 문제를 풀어야한다. 숫자의 특성에 따라 수를 분리하면 1보다 큰 양수, 1, 0, 음수 총 4가지로 나눌 수 있다.

• 1보다 큰 양수일 경우 더하는 것보다 곱하는 것이 더 큰 값을 만든다. 또한 여러 양수가 있을 때 가장 큰 두 수를 곱하는 것이 최댓값을 준다.
• 음수일 경우 더하는 것보다 곱하여 부호를 양수로 만드는 것이 더 큰값을 만든다. 또한 가장 작은 두 수를 곱해야 최댓값을 만들 수 있다.
  • 만약 음수가 1개 남는다면 0이 있는지 확인한다 만약 0이 있다면 두 수를 곱하는 것이 더하는 것보다 최댓값 만드는 것에 도움이 된다.
• 마지막으로 남은 1의 갯수만큼 결과에 더해준다.

package 백준;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
 
* */
public class 수묶기_1744 {
    public static void main(String[] args) throws IOException {
        int max = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());    // 큰 수가 먼저 나오게
        PriorityQueue<Integer> mQ = new PriorityQueue<>();  // 작은 수가 먼저 나오도록
        int one = 0;
        int zero = 0;
 
        int num;
        for (int i=0; i<N; i++) {
            num = Integer.parseInt(br.readLine());
 
            if (num > 1) pQ.add(num);
            else if (num == 1) one++;
            else if (num == 0) zero++;
            else mQ.add(num);
        }
 
        while (pQ.size() >= 2) {
            int num1 = pQ.poll();
            int num2 = pQ.poll();
            max += num1*num2;
        }
        if (pQ.size() == 1) {
            max += pQ.poll();
        }
 
        while (mQ.size() >= 2) {
            int num1 = mQ.poll();
            int num2 = mQ.poll();
            max += num1*num2;
        }
        if (mQ.size() == 1) {
            if (zero == 0) {
                max += mQ.poll();
            }
        }
 
        max += one;
 
        System.out.println(max);
    }
}