[백준] 1744 수 묶기

문제 출처: www.acmicpc.net/problem/1744

1744번: 수 묶기

: 길이가 N인 수열이 주어지고 수열의 합을 구해야한다.

: 단순히 수열에 있는 수들의 합이 아니고 각각의 수를 한번씩 묶을 수 있도록 하고 묶은 수는 서로 곱한 후에 더한다.

: 따라서 모든 수는 한번만 묶이거나 묶지 않아야 한다.

: 이러한 규칙에 따라 각각의 수를 적절히 묶을 때 그 합이 최대가 되도록 해야한다.

 

: 먼저 수열의 길이인 N을 입력받는다.

: 수열을 구성하는 숫자들을 입력받아 배열에 저장한다.

: 배열을 순회하며 0이하의 수들과 0을 초과하는 수들을 나눠 각각의 nagative, positive 배열에 저장한다.

: negative 배열의 경우 숫자가 작은 것이 서로 곱해져서 양수가 되면 가장 큰수가 되기 때문에 작은 수부터 접근하여 계산해 줄 수 있도록한다.

: positive인 경우 1은 곱하는 것보다 더하는 것이 수가 더 커지는 방향이므로 이러한 경우들을 모두 고려하여 계산한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 숫자의 개수를 입력받고
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		// 숫자 개수만큼 숫자들을 입력받고
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		// 정렬시켜서
		Arrays.sort(arr);
		int idx = 0;
		if(arr[0] > 0) idx = 0;
		else if(arr[N-1] <= 0) idx = N;
		else {
			// 몇번째 인덱스부터 양수가 시작되는지를 찾음
			for(int i = 0; i < N; i++ ) {
				if(arr[i] > 0) {
					idx = i;
//					System.out.println("dd");
					break;
				}
			}			
		}

		// 음수 양수가 나눠지는 기점부터 큰수를 묶기 시작함
		int[] negative = Arrays.copyOfRange(arr, 0, idx);
		int[] positive = Arrays.copyOfRange(arr, idx, N);
//		System.out.println("idx = " + idx);
//		System.out.println("negative"+Arrays.toString(negative));
//		System.out.println("positive"+Arrays.toString(positive));
		int total = 0;
		for(int i = 0, size = negative.length; i < size; i+=2) {
			if(i+1 < size) {
				total += negative[i]*negative[i+1];				
			}else {
				total += negative[i];
			}
		}
		int index = positive.length-1;
		while(index >= 0) {
//			System.out.println("arr = " + arr[index]);
			if(index-1 < 0 || positive[index] == 1 || (index-1 >= 0 && positive[index-1] == 1)) {
				total += positive[index];
				index--;
//				System.out.println(total);
			}else if(index-1 >= 0 && positive[index-1] != 1){
				total += positive[index] * positive[index-1];
				index -= 2;
			}
		}
		System.out.println(total);
		//-1 -2 -3 0 1 2 3
		
	}
}