[BOJ/Greedy] 백준 1744 - 수 묶기 (Java)

1744 - 수 묶기

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

문제

길이가 N인 수열 -> 수열의 두 수를 묶어서 그 수열의 합
어떤 수를 묶으려고 할 때, 위치에 상관 X 묶을 수 있음
But, 같은 위치에 있는 수(자기자신)를 묶는 것을 불가능
어떤 수를 묶게 되면, 서로 곱한 후에 더함
ex. {0, 1, 2, 4, 3, 5} -> 합: 0+1+2+4+3+5 = 15
But, 2와 3, 4와 5 묶으면 -> 0+1+(2*3)+(4*5) = 27 최대
수열의 모든 수는 단 한번만 묶거나 아니면 묶지 않아야 함

=> 수열이 주어졌을 때, 각 수를 적절히 묶었을 때 최대합?

입력
첫째 줄: 수열의 크기 N (N (자연수) <= 50)
둘째 줄부터 N개의 줄: 수열의 각 수가 주어짐 
(-1,000 <= 수열의 수 (정수) <= 1,000)
출력: 합이 최대가 나오게 묶었을 때 합 (< $2^{31}$)

---

풀이

양수끼리 묶어서 곱하기 or 음수끼리 묶어서 곱하기 

• `plusPQ`: 2 이상의 양수를 큰 순서대로 저장
  • 큰 수끼리 묶어서 곱할수록 커짐
• `minusPQ`: 음수를 작은 순서대로 저장
  • 작은 수끼리 곱할 수록 커짐

=> 각각 짝수 개씩 모두 곱해서 처리

홀수 개일 경우 -> 양수: 더하기/ 홀수: 0으로 무효화 or 더하기

 

• `ones`: 1은 곱하는 것보다 더하는 것이 커짐
• `zeros`: 음수가 1개 남았을 경우 무효화용

---

코드

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

// 수 묶기
public class boj_1744 {
    public static int calculate(PriorityQueue<Integer> pq) {
        int sum = 0;

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            sum += a * b;
        }

        return sum;
    }

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

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> plusPQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minusPQ = new PriorityQueue<>();
        int ones = 0;
        int zeros = 0;

        while (N-- > 0) {
            int num = Integer.parseInt(br.readLine());
            if (num > 1) plusPQ.add(num);
            else if (num == 1) ones++;
            else if (num == 0) zeros++;
            else minusPQ.add(num);
        }

        int result = 0;
        result += calculate(plusPQ);
        if (!plusPQ.isEmpty()) result += plusPQ.poll();

        result += calculate(minusPQ);
        if (!minusPQ.isEmpty()) {
            if (zeros > 0) zeros--;
            else result += minusPQ.poll();
        }

        result += ones;

        System.out.println(result);
    }
}