[JAVA][Baekjoon] 1744번 수 묶기 🌟🌟🌟

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

📌 접근 방식

주어진 수열에서 합을 최대화하기 위해 단순히 더하는 대신, 수를 적절히 묶어서 곱하거나 더하는 방식을 사용해야 함

 

1️⃣ 양수와 음수를 분리

• 양수 중 1보다 큰 수는 곱할수록 값이 커지므로 큰 수들끼리 묶어야 한다.
• 1은 곱하기보다 더하기가 유리하므로 묶지 않고 따로 더한다.

2️⃣ 음수와 0 처리

• 음수는 절댓값이 큰 수들끼리 묶어서 곱하면 양수가 됨
• 0은 음수와 묶어서 0으로 만들 수 있으므로 활용

3️⃣ 우선순위 큐(Priority Queue) 활용

• 양수와 음수를 각각 정렬된 형태로 저장하고, 묶을 때 효율적으로 처리
• 큐를 사용해 큰 양수, 작은 음수를 빠르게 꺼내며 계산함

[알고리즘] 그리디 알고리즘(Greedy Algorithm)

 

✅ PASS CODE

import java.io.*;
import java.util.Collections;
import java.util.PriorityQueue;

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()); // 수열의 크기
        PriorityQueue<Integer> minuspq = new PriorityQueue<>(); // 음수 저장
        PriorityQueue<Integer> pluspq = new PriorityQueue<>(Collections.reverseOrder()); // 양수 저장
        int one = 0; // 1의 개수
        int zero = 0; // 0의 개수
        
        // 수 입력 및 분류
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num > 1) {
                pluspq.add(num); // 1보다 큰 양수
            } else if (num == 1) {
                one++; // 1은 따로 더함
            } else if (num == 0) {
                zero++; // 0
            } else {
                minuspq.add(num); // 음수
            }
        }

        int sum = 0;

        // 1️⃣ 양수 처리: 큰 값부터 곱해서 누적
        while (pluspq.size() > 1) {
            int first = pluspq.remove();
            int second = pluspq.remove();
            sum += first * second;
        }
        if (!pluspq.isEmpty()) {
            sum += pluspq.remove(); // 남은 양수 추가
        }

        // 2️⃣ 음수 처리: 작은 값부터 곱해서 누적
        while (minuspq.size() > 1) {
            int first = minuspq.remove();
            int second = minuspq.remove();
            sum += first * second;
        }
        if (!minuspq.isEmpty() && zero == 0) {
            sum += minuspq.remove(); // 남은 음수 처리 (0 없으면 더함)
        }

        // 3️⃣ 1은 곱하지 않고 그냥 더하기
        sum += one;

        System.out.println(sum); // 결과 출력
    }
}

 

• 우선순위 큐를 사용해 양수는 내림차순, 음수는 오름차순으로 정렬
• 묶을 수 있는 수가 하나만 남았을 경우 예외 처리를 통해 추가하거나 생략
• 1과 0은 별도로 처리하여 최대 합을 보장함

 

 

😊 느낀 점

처음에는 단순히 수열을 정렬해서 양수는 큰 값끼리, 음수는 작은 값끼리 곱하면 된다고 생각했다. 하지만 문제 조건에 따라 0과 음수를 어떻게 처리하느냐에 따라 결과가 크게 달라진다는 점을 알게 되었다.

또한, 그리디 알고리즘이 최적의 해를 보장하려면 특정 조건이 필요하다는 사실을 다시 한번 느꼈다. 이 문제에서는 큰 양수는 곱하고, 음수는 짝수 개로 묶는 규칙이 최적의 해를 보장한다는 점이 핵심이었다.