백준 1744 자바(java) 수 묶기

문제

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작은 자연수이다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

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

public class Main {	
	static Integer[] arr;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		arr = new Integer[n];
		int sum = 0;
		for(int i = 0; i<arr.length; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Arrays.sort(arr); 	// 음수값들 더하기 위해 오름차순 정렬
		if(countMinus()%2 ==0) {	 // 음수 갯수가 짝수일 때
			for(int i = 0; i<arr.length && arr[i]<=0;) { 	
				sum += arr[i]*arr[i+1];
				i += 2;		//다음 인덱스를 더한 값까지 i를 두번 더해준다.
			}
		}
		else {		음수 갯수가 홀수일 때
			for(int i = 0; i<arr.length && arr[i]<=0;) {
				if(i+1 == countMinus()) {		//마지막 인덱스일 경우
					if(arr[i] == 0) {		//음수 갯수가 홀수에다가 마지막 인덱스가 0이면 (ex. -3, -3, -3, 0 일경우 최댓값은 9이다.) 이전 인덱스 값을 다시 -하여 준 후 반복문 중지
						sum -= arr[i-1];
						break;
					}
					sum += arr[i];
					break;
				}
				else {
					sum += arr[i]*arr[i+1];
					i += 2;	//다음 인덱스를 더한 값까지 i를 두번 더해준다.
				}
			}
		}
		
		Arrays.sort(arr, Collections.reverseOrder()); //양수값들을 더하기 위해 내림차순 정렬
		if(countPlus()%2 ==0) {		// 양수 갯수가 짝수일 때
			for(int i = 0; i<arr.length && arr[i]>0;) {
				if(arr[i+1] == 1) {		//인덱스 값 중 1이 존재할 경우 곱하지 않고 1을 더해주어야 최댓값이 된다.
					sum += arr[i] + arr[i+1];
					i += 2;
				}
				else {
					sum += arr[i]*arr[i+1];
					i += 2;
				}
			}
		}
		else {		//양수 갯수가 홀수일때
			for(int i = 0; i<arr.length && arr[i]>0;) {
				 if( i+1 == countPlus()) {
					sum += arr[i];
					break;
				}
				else {
					if(arr[i+1] == 1) {
						sum += arr[i];
						i++;
					}
					else {
						sum += arr[i]*arr[i+1];
						i += 2;
					}
				}
			}
		}
		System.out.println(sum);
	}
	
	static int countMinus() {
		int count = 0;
		for(int i = 0; i< arr.length; i++) {
			if(arr[i] <= 0) {
				count++;
			}
		}
		return count;
	}
	static int countPlus() {
		int count = 0;
		for(int i = 0; i< arr.length; i++) {
			if(arr[i]>0) {
				count ++;
			}
		}
		return count;
	}
}

풀이

음수 * 음수 = 양수가 되므로 음수끼리 최대한 곱한 값과

양수 * 양수 를 최대한 곱한 값을 더해주면 된다.

나는 음수부분의 합을 구하기위해 sort로 오름차순 정렬 후 음수의 갯수가 짝수/홀수 일 경우의 합과

양수부분의 합을 구하기위해 내림차순 정렬로 양수의 갯수가 짝수/ 홀수일 경우의 합을 더해 sum에 더하여 주었다.

이 문제는 반례가 상당히 많아 반례를 참고하기 바란다.

https://bingorithm.tistory.com/3

"백준 1744번-수 묶기" 반례 모음