[백준] 1744번 : 수 묶기 - JAVA [자바]

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

그리디 알고리즘 문제이다.

합을 최대로 만드려면 양수 x 양수 , 음수 x 음수, 음수 x 0 을 한 뒤 더해야 한다.

1. 양수와 음수 + 0 배열을 구분하여 입력을 받는다.
2. 양수 배열은 오름차순으로 정렬하여 큰 수끼리 먼저 곱하여 최대로 만들도록 한다.
3. 음수 배열은 내림차순으로 정렬하여야 절대값이 큰 수부터 정렬된다.
4. 양수 배열에서 다음 수가 있는지 판단하여 있다면 곱하여 합을 더 해주며 없다면 자기 자신만 더하여 합을 구해준다.
5. 음수 배열에서도 다음 수가 있는지 판단하여 있다면 곱하여 합에 더해주고 없다면 자기 자신을 더하여 합을 구해준다.

이때 주의할 점이 하나 있다. 양수 배열에서 1을 곱하는 경우를 생각해보자 만약 3, 1 이렇게 양수 배열이 있다고 할 때, 3x1은 3이고 3+1은 4이다. 즉, 묶는 수가 1일 경우 묶어서 곱하지 말고 덧셈을 해야 더 큰 수를 얻을 수 있다는 것이다.

public class bj1744 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        List<Integer> pn = new ArrayList<>();
        List<Integer> nn = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num > 0) {
                pn.add(num);
            } else nn.add(num);
        }

        // 큰 수부터 곱하기
        pn.sort(Collections.reverseOrder());
        // 절대값이 큰 수부터 곱하기
        Collections.sort(nn);

        int answer = 0;
        for (int i = 0; i < pn.size(); i++) {
        	// 1일 경우 유의!!
            if (i + 1 < pn.size() && pn.get(i) != 1 && pn.get(i + 1) != 1) {
                answer += pn.get(i) * pn.get(i + 1);
                i++;
            } else answer += pn.get(i);
        }
        
        for (int i = 0; i < nn.size(); i++) {
            if (i + 1 < nn.size()) {
                answer += nn.get(i) * nn.get(i + 1);
                i++;
            } else answer += nn.get(i);
        }

        System.out.println(answer);
        br.close();
    }
}