링크

링크텍스트

문제

n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 정수의 곱이 점수가 된다. 이를 반복하여 수열에 아무 수도 남지 않게 되었을 때, 점수의 총 합의 최대를 구하는 프로그램을 작성하시오.

예를 들어 -1, 5, -3, 5, 1과 같은 수열이 있다고 하자. 먼저 1을 제거하고, 다음으로는 5와 5를 제거하고, 다음에는 -1과 -3을 제거했다고 하자. 이 경우 각각 점수가 1, 25, 3이 되어 총 합이 29가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 절댓값이 1,000,000을 넘지 않는 정수가 n개 주어진다.

출력

첫째 줄에 최대 점수를 출력한다.

풀이

이 문제는 n개의 정수가 절대값이 1,000,000까지 될 수 있으므로 정수가 어마어마하게 커질 우려가 크다. 그렇기 때문에 long, double이 아닌
BigInteger 타입을 써야한다. 그리고 값 정수, 음수, 1의 배열들을 만들어준다. 만약 정수나 음수의 배열의 길이가 짝수개라면 2개씩 곱해주지만 배열의 길이가 홀수개라면 2개씩 곱해주다가 나머지 1개는 그냥 더해주기만 하면된다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class practice {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		BigInteger answer=new BigInteger("0");
		
		ArrayList<Long> plus=new ArrayList<Long>();
		ArrayList<Long> minus=new ArrayList<Long>();
		ArrayList<Long> one=new ArrayList<Long>();
		
		for(int i=0; i<n; i++)
		{
			long num=Integer.parseInt(br.readLine());
			if(num==1)
				one.add(num);
			else if(num>1)
				plus.add(num);
			else if(num<=0)
				minus.add(num);
		}
		
		Collections.sort(plus, Collections.reverseOrder());
		Collections.sort(minus);
		
		if(plus.size()%2==0)
		{
			for(int i=0; i<plus.size(); i+=2)
				answer=answer.add(BigInteger.valueOf(plus.get(i)*plus.get(i+1)));
		}
		
		else if(plus.size()%2!=0)
		{
			for(int i=0; i<plus.size()-1; i+=2)
				answer=answer.add(BigInteger.valueOf(plus.get(i)*plus.get(i+1)));
			answer=answer.add(BigInteger.valueOf(plus.get(plus.size()-1)));
		}
		
		if(minus.size()%2==0)
			for(int i=0; i<minus.size(); i+=2)
				answer=answer.add(BigInteger.valueOf(minus.get(i)*minus.get(i+1)));
		
		else if(minus.size()%2!=0)
		{
			for(int i=0; i<minus.size()-1; i+=2)
				answer=answer.add(BigInteger.valueOf(minus.get(i)*minus.get(i+1)));
			answer=answer.add(BigInteger.valueOf(minus.get(minus.size()-1)));
		}
		
		long one_size=one.size();
		answer=answer.add(BigInteger.valueOf(one_size));
		System.out.println(answer);
		
		
	}
}