[백준] 1744번 - 수 묶기 [Java]

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

 

[백준] 1744번 - 수 묶기 [Java]

[백준] 1744번 - 수 묶기 [Java]

[백준] 1744번 - 수 묶기 [Java]

---

1.  아이디어

 

그리디 알고리즘으로 해결할 수 있다.
1 보다 큰 정수는 값이 큰 정수부터 2개씩 묶을수록 최대가 되고, 1은 그냥 더할 때 최대가 된다.
0 이하인 정수는 절댓값이 큰 정수부터 2개씩 묶을수록 최대가 된다.

---

2. 문제풀이

 

1 보다 큰 정수를 담은 우선순위 큐와 0 이하인 정수를 담은 우선순위 큐 두 개를 활용했다.
1은 따로 담지 않고 바로 더해줬다.
1 보다 큰 정수를 담은 우선순위 큐는 절댓값이 큰 수부터 묶어야하므로 우선순위 큐의 길이가 홀수면 앞의 수 하나는 빼서 그냥 더하고 나머지는 묶는 식으로 구현했고,
0 이하인 정수를 담은 우선순위 큐도 절댓값이 큰 수부터 묶어야하므로 하나밖에 안남아서 묶을 수 없으면 그냥 더하는 조건을 추가했다.

---

3. 코드

 

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());

        // 1 보다 큰 정수만 담는 우선순위 큐
        PriorityQueue<Integer> pos_pq = new PriorityQueue<>();

        // 0 이하인 정수만 담는 우선순위 큐
        PriorityQueue<Integer> neg_pq = new PriorityQueue<>();

        int sum = 0;

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            if (num > 1) pos_pq.add(num);
            else if (num == 1) sum += num;
            else neg_pq.add(num);
        }

        // 0 이하인 정수는 작은 수부터 최대한 짝을 맞추면 됨
        while (!neg_pq.isEmpty()) {
            int num1 = neg_pq.remove();

            if (neg_pq.isEmpty()) {
                sum += num1;
                break;
            }

            int num2 = neg_pq.remove();

            sum += num1 * num2;
        }

        // 1 보다 큰 정수는 큰 수부터 최대한 짝을 맞추면 됨
        if (pos_pq.size() % 2 == 1) sum += pos_pq.remove();

        while (!pos_pq.isEmpty()) {
            int num1 = pos_pq.remove();
            int num2 = pos_pq.remove();
            sum += num1 * num2;
        }

        System.out.println(sum);
    }
}

---

4. 후기