[백준] 1744. 수 묶기

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

1744번: 수 묶기

• 그리디 문제로, 어떻게 하면 제일 큰 결과 값을 구할 수 있을지 아이디어만 잘 생각하면 된다.
• 음수의 경우
  • 음수끼리 묶어서 곱해주어야 양수가 되어 결과 값이 커진다.
  • 그리고 이때 절댓값이 큰 음수끼리 우선적으로 묶어주어야 결과가 더 크다.
  • 따라서 음수를 minus 리스트에 모아서 minus 리스트를 오름차순하고 순차적으로 묶어준다.
  • 만약 두개의 음수를 묶고 묶이지 않은 음수가 1개 남는다면, 이 음수를 0이 있으면 0과 곱해주어야 하고, 0이 없으면 어떤 수와도 묶지 말고 더해주어야 한다.
  • 따라서 음수뿐만 아니라 0도 minus 리스트에 담아야 한다.
  • minus 리스트를 오름차순하고 앞에서부터 순차적으로 묶어줄 때 마지막에 묶이지 않은 1개의 수가 있다면, 이는 음수 또는 0일 것이다. 따라서 이 수는 양수와 묶는 것보다 더하는 것이 결과 값이 더 크다.
• 양수의 경우
  • 1과 2 이상의 양수를 나누어 생각해야 한다. 1의 경우 "음수", "0", "2 이상의 양수" 어떤 것과도 곱하는 것보다 더하는 것이 결과 값이 더 크다.
  • 따라서 1은 따로 oneCount라는 변수를 두어 1의 개수를 계산한다.
  • 그리고 2 이상의 양수는 값이 큰 수끼리 우선적으로 묶어주어야 결과가 더 크다.
  • 따라서 1을 제외한 양수를 plus 리스트에 모아서 plus 리스트를 내림차순하고 순차적으로 묶어준다.

import java.io.BufferedReader;
import java.io.IOException;

import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 시간복잡도: O(N) = 50
public class Main {

    static int n;
    static List<Integer> plus = new ArrayList<>();
    static List<Integer> minus = new ArrayList<>();
    static int oneCount = 0;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        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 <= 0) {
                minus.add(num);
            } else if (num == 1) {
                oneCount++;
            } else {
                plus.add(num);
            }
        }

        // 1. 음수: 오름차순
        Collections.sort(minus);
        // 1 - 1. 절댓값 큰 음수끼리 묶기
        // 1 - 2. 2개로 묶이지 않은 하나의 수는 음수 또는 0, 이 수는 묶지 말고 더하기
        for (int i = 0; i < minus.size(); i += 2) {
            if (i == minus.size() - 1) {
                answer += minus.get(i);
                break;
            }
            answer += minus.get(i) * minus.get(i + 1);
        }

        // 2. 양수: 내림차순
        Collections.sort(plus, Collections.reverseOrder());
        for (int i = 0; i < plus.size(); i += 2) {
            if (i == plus.size() - 1) {
                answer += plus.get(i);
                break;
            }
            answer += plus.get(i) * plus.get(i + 1);
        }

        // 3. 1인 경우: 묶지 말고 더하기
        answer += oneCount;

        System.out.println(answer);
    }
}