[백준] 1744번 - 수 묶기 (Gold 4)

문제 링크

백준 1744번 - 수 묶기 (Gold 4)

문제 설명

길이가 N인 수열이 주어져 있다.
수열의 두 수를 묶거나 묶지 않을 수 있는데, 자기 자신과는 묶을 수 없다.
또한 수열의 각 수는 최대 한 번만 묶을 수 있다.
수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다고 할 때, 가능한 수열의 합의 최댓값을 구하시오.

예를 들어 수열 {0, 1, 2, 4, 3, 5}의 합의 최댓값은 $0 + 1 + (2 \times 3) + (4 \times 5) = 27$이다.

정답 코드 및 설명

수열의 값 중 음수인 항과 양수인 항을 나누어서 생각하자.
양수인 항들의 합의 최댓값은 1은 무조건 묶지 않고, 그 이상은 가장 큰 항부터 두 개씩 묶어서 구한 합이다.
음수인 항들의 합의 최댓값은 두 가지 경우로 나뉜다.

1. 음수인 항이 짝수 개인 경우의 최댓값
   • 절댓값이 가장 큰 항부터 두 개씩 묶는다.
2. 음수인 항이 홀수 개인 경우의 최댓값
   • 0이 없다면 : 절댓값이 가장 작은 항은 그냥 더한다.
   • 0이 있다면 : 절댓값이 가장 작은 항과 0을 묶는다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class BOJ1744 {
    int n;
    int numOfZeros = 0;
    int numOf1 = 0;
    ArrayList<Integer> biggerThan1 = new ArrayList<>();
    ArrayList<Integer> negative = new ArrayList<>();

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int curr = Integer.parseInt(br.readLine());
            if (curr == 0) numOfZeros++;
            if (curr == 1) numOf1++;
            if (curr > 1) biggerThan1.add(curr);
            if (curr < 0) negative.add(curr);
        }
        Collections.sort(biggerThan1);
        negative.sort(Collections.reverseOrder());
    }

    int maxOfPositive() {
        int maxOfPositive = 0;
        int size = biggerThan1.size();
        int start = size % 2;
        for (int i = start; i < size; i += 2) {
            maxOfPositive += biggerThan1.get(i) * biggerThan1.get(i + 1);
        }
        if (start == 1) maxOfPositive += biggerThan1.get(0);
        maxOfPositive += numOf1;
        return maxOfPositive;
    }

    int maxOfNegative() {
        int maxOfNegative = 0;
        int size = negative.size();
        int start = size % 2;
        for (int i = start; i < size; i += 2) {
            maxOfNegative += negative.get(i) * negative.get(i + 1);
        }
        if (start == 1 && numOfZeros == 0)
            maxOfNegative += negative.get(0);
        return maxOfNegative;
    }

    void solution() throws IOException {
        input();
        System.out.println(maxOfPositive() + maxOfNegative());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1744().solution();
    }
}