[Algorithm] 😀백준 1744 수 묶기

0. 문제

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

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

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

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

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

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

1. 아이디어

💡 음수와 양수를 별도로 구분함
💡 양수는 내림차순하여 곱한 후, 양수가 홀수개라면 나머지 수를 더해줌
💡 음수는 오름차순하여 곱한 후, 0을 고려하여 나머지 수를 더할지 말지 결정함
💡 0이 있고 음수의 개수가 홀수이면 두 개를 곱해 0으로 만들 수 있음
💡 1은 어떤 수와 곱하는 것보다 더하는 것이 더 큼

2. 핵심 풀이

1. 음수와 양수를 별도로 구분함

ArrayList<Integer> plus = new ArrayList<>();
ArrayList<Integer> minus = new ArrayList<>();
		
for(int i=0; i<n; i++) {
	if(arr[i] < 0) {
		minus.add(arr[i]);
		arr[i] = 0;
	}
			
	plus.add(arr[i]);
}

2. 양수는 내림차순하여 곱한 후, 양수가 홀수개라면 나머지 수를 더해줌

for(int i=0; i<pSize/2; i++) {
	int a = plus.remove(0);
	int b = plus.remove(0);
	if(a == 1 || b == 1) {
		sum += (a+b);
	} else {
		sum += (a*b);
	}
}
		
if(pSize % 2 != 0) {
	sum += plus.remove(0);
}

3. 음수는 오름차순하여 곱한 후, 0을 고려하여 나머지 수를 더할지 말지 결정함

for(int i=0; i<mSize/2; i++) {
	int a = minus.remove(0);
	int b = minus.remove(0);
	sum += (a*b);
}

4. 0이 있고 음수의 개수가 홀수이면 두 개를 곱해 0으로 만들 수 있음

if(zero == -1 && mSize % 2 != 0) {
	sum += minus.remove(0);
}

3. 코드

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

public class BOJ_1744 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int zero = -1;
		Integer[] arr = new Integer[n];
		
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			if(arr[i] == 0) zero = 1;
		}
		
		Arrays.sort(arr, Collections.reverseOrder());
		
		ArrayList<Integer> plus = new ArrayList<>();
		ArrayList<Integer> minus = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			if(arr[i] < 0) {
				minus.add(arr[i]);
				arr[i] = 0;
			}
			
			plus.add(arr[i]);
		}
		
		plus.removeAll(Arrays.asList(Integer.valueOf(0)));
		
		Collections.sort(minus);
		
		int pSize = plus.size();
		int mSize = minus.size();
		int sum = 0;
		
		for(int i=0; i<pSize/2; i++) {
			int a = plus.remove(0);
			int b = plus.remove(0);
			if(a == 1 || b == 1) {
				sum += (a+b);
			} else {
				sum += (a*b);
			}
		}
		
		if(pSize % 2 != 0) {
			sum += plus.remove(0);
		}
		
		for(int i=0; i<mSize/2; i++) {
			int a = minus.remove(0);
			int b = minus.remove(0);
			sum += (a*b);
		}
		
		if(zero == -1 && mSize % 2 != 0) {
			sum += minus.remove(0);
		}
		
		System.out.println(sum);
	}

}

4. 결과

성공✨