[BaekJoon] 2036 수열의 점수

1.  문제 링크

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

2.  문제

요약

• n개의 정수로 이루어진 수열에서 정수 한 개 또는 두 개를 제거할 수 있습니다.
• 한 개의 정수를 제거하는 경우는 그 정수가 점수가 됩니다.
• 두 개의 정수를 제거하는 경우는 두 정수의 곱이 점수가 됩니다.
• n개의 정수로 이루어진 수열이 주어졌을 때, 해당 수열에 아무 수도 남지 않을 때까지 반복하며 점수의 총 합이 최대로 되도록 정수를 제거해가는데 이 때 점수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 n이 주어지고 두 번째 줄부터 n개의 줄에는 1,000,000보다 작거나 같은 정수 n개가 주어집니다.
• 출력: 첫 번째 줄에 최대 점수를 출력합니다.

3.  소스코드

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

public class Main {
	public long getMaxPoint(ArrayList<Integer> positive, ArrayList<Integer> negative, ArrayList<Integer> zero) {
		Collections.sort(positive, Collections.reverseOrder());
		Collections.sort(negative);
		long point = 0;
		if(positive.size() != 0 && positive.size() % 2 != 0) {
			point += positive.get(positive.size() - 1);
			positive.remove(positive.size() - 1);
		}
		if(negative.size() != 0 && negative.size() % 2 != 0) {
			if(zero.size() == 0) {
				point += negative.get(negative.size() - 1);
			}
			negative.remove(negative.size() - 1);
		}
		for(int i = 0; i < positive.size(); i += 2) {
			if(positive.get(i) == 1 || positive.get(i + 1) == 1) {
				point += positive.get(i) + positive.get(i + 1);
			} else {
				point += (positive.get(i) * (long)positive.get(i + 1));
			}
		}
		for(int i = 0; i < negative.size(); i += 2) {
			point += (negative.get(i) * (long)negative.get(i + 1));
		}
		return point;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		ArrayList<Integer> positive = new ArrayList<Integer>();
		ArrayList<Integer> negative = new ArrayList<Integer>();
		ArrayList<Integer> zero = new ArrayList<Integer>();
		for(int i = 0; i < num; i++) {
			int temp = Integer.parseInt(br.readLine());
			if(temp > 0) {
				positive.add(temp);
			} else if(temp < 0) {
				negative.add(temp);
			} else {
				zero.add(temp);
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxPoint(positive, negative, zero) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 점수를 최대로 하기 위해서는 점수에서 최대한 음수를 줄이고 큰 수를 얻기 위해 큰 수들끼리 곱셈을 진행하여 이 점수들을 더해야 합니다.
• 음수끼리의 곱을 통해 양수를 만들어나가며 점수를 올려야하고 음수를 줄이기 위해 0과 곱하여 음수를 0으로 변경해야 하므로 수열들을 양수, 0, 음수 세 가지 분류를 따로 세 개의 배열에 저장하여 문제를 풀어갑니다.
• 음수를 최대한 줄이기 위해서는 음수끼리 곱셈을 하여 양수로 만드는 방법과 수열에 0이 있을 경우 0과 곱하여 음수를 0으로 만드는 방법이 있습니다.
• 점수를 최대로 하기 위해 음수끼리 큰 수들부터 곱셈을 진행하여 점수를 늘려나갑니다.
• 2개의 음수들을 곱해가다가 마지막에 하나의 음수가 남는 경우, 수열에 0이 존재한다면 0과 곱하여 해당 음수를 0으로 만들고 그렇지 않다면 마지막에 남는 음수를 점수에 더합니다. 이 때 남은 음수는 큰 수들부터 곱해나가기 때문에 해당 수열의 음수 중에서 절댓값이 가장 작은 음수가 됩니다.
• 큰 수들끼리의 곱셈을 진행하기 위해 양수, 음수 배열은 각각 내림차순, 오름차순으로 정렬하여 문제를 풀어갑니다.

1. 주어진 수열의 수들을 양수, 음수, 0으로 나누어 담기 위해 positive, negative, zero라는 3개의 ArrayList를 생성하고 수들을 각각 맞는 ArrayList에 저장합니다.
2. 큰 수부터 차례대로 곱해나가기 위해 negative ArrayList는 오름차순으로 정렬하고 positive ArrayList는 내림차순으로 정렬합니다.
3. 양수의 개수가 홀수인 경우, positive ArrayList의 가장 마지막 수, 즉 양수 중 가장 작은 수는 점수에 더해줍니다.
4. 음수의 개수가 홀수인 경우에는
• zero ArrayList의 개수가 0이 아닌 경우, 즉 0의 개수가 0이 아닌 경우는 negative ArrayList의 가장 마지막 수, 즉 음수 중 절댓값이 가장 작은 수는 0과 곱하여 0이 되도록 합니다.
• zero ArrayList의 개수가 0인 경우, 즉 0의 개수가 0인 경우에는 negative ArrayList의 가장 마지막 수, 즉 음수 중 절댓값이 가장 작은 수를 점수에 더해줍니다.
5. 양수와 음수 모두 가장 절댓값이 큰 수부터 차례대로 내려가며 절댓값이 큰 순서대로 2개씩 곱하고 해당 수를 점수에 더해줍니다.
6. 이렇게 구한 점수를 출력합니다.