[백준] 1744: 수 묶기 - JAVA

in Algorithm on 그리디 알고리즘

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

풀이

길이 n의 수열이 주어지고, 이 수열의 합을 구하는 문제이다.

수열내의 두 수를 묶어 그 수들을 곱하는 것으로 계산 할 수 있다.

{-1, 2, 1, 3} 과 같은 수열이 있다면, 2와 3을 묶어 6으로 만들고,

-1 + 1 + 6 = 6 으로 6이 최대값이 된다.

음수는 같은 음수끼리 곱하거나, 0과 곱할 때 합에서 이득을 볼 수 있으므로

0이하인 것들은 minus 리스트에 담고, 0보다 큰 수들은 plus 리스트에 담았다.

두 리스트를 정렬해서 minus에 있는 것들은 작은 순으로 2개씩 묶고,

plus에 있는 수들은 큰 순으로 2개씩 묶었다.

다만, 1의 경우는 {1, 1} 의 수열에서 볼 때, 1 + 1 이 1 * 1 보다 크므로 안 묶는 것이 이득이다. 이를 고려하여 계산하면 정답이 나온다.

메모리: 14364KB

시간: 128ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> plus = new ArrayList<>();
        ArrayList<Integer> minus = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num <= 0) {
                minus.add(num);
            } else {
                plus.add(num);
            }
        }
        Collections.sort(plus, Collections.reverseOrder());
        Collections.sort(minus);

        ArrayList<Integer> sum = new ArrayList<>();
        for (int i = 0; i < plus.size(); i += 2) {
            int a = plus.get(i);
            int b = 0;
            if (i + 1 < plus.size()) {
                b = plus.get(i + 1);
            }
            if (b > 1) {
                sum.add(a * b);
            } else {
                sum.add(a);
                sum.add(b);
            }
        }

        for (int i = 0; i < minus.size(); i += 2) {
            int a = minus.get(i);
            int b = 1;
            if (i + 1 < minus.size()) {
                b = minus.get(i + 1);
            }
            sum.add(a * b);
        }

        int answer = sum.stream().mapToInt(i -> i).sum();

        System.out.println(answer);
    }

}