[BaekJoon] 1744 수 묶기 (Java)

1.  문제 링크

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

2.  문제

요약

• 길이가 N인 수열이 주어졌을 때, 수열의 두 수를 묶어 서로 곱한 후에 더하여 수열의 합을 구하려고 합니다.
• 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있지만 자기 자신을 묶는 것은 불가능합니다.
• 수열의 모든 수는 단 한번만 묶거나, 묶지 않아야 합니다.
• 수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 문제입니다.
• 입력: 첫 번째 줄에 50보다 작은 자연수인 수열의 크기 N이 주어지고 두 번째 줄부터 N개의 줄에는 -1,000보다 크거나 같고 1,000보다 작거나 같은 정수인 수열의 각 수가 주어집니다.
• 출력: 첫 번째 줄에 수를 합이 최대가 나오게 묶었을 때 합을 출력합니다.
  • 정답은 항상 $2^{31}$보다 작습니다.

3.  소스코드

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

public class Main {
	static int N;
	static ArrayList<Integer> positive, negative;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		positive = new ArrayList<Integer>();
		negative = new ArrayList<Integer>();
		for(int i = 0; i < N; i++) {
			int temp = scanner.nextInt();
			if(temp > 0) positive.add(temp);
			else negative.add(temp);
		}
	}
	
	static void solution() {
		Collections.sort(positive, Collections.reverseOrder());
		Collections.sort(negative);
		int total = 0, idx = 0;
		while(idx < positive.size()) {
			if(idx + 1 < positive.size() && positive.get(idx) != 1 && positive.get(idx + 1) != 1)
				total += positive.get(idx++) * positive.get(idx++);
			else total += positive.get(idx++);
		}
		idx = 0;
		boolean flag = true;
		while(idx < negative.size()) {
			if(idx + 1 < negative.size()) total += negative.get(idx++) * negative.get(idx++);
			else total += negative.get(idx++);
		}
		System.out.println(total);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 주어진 N개의 수를 양수인 수와 그렇지 않은 수로 나눠 따로 저장합니다.
• 두 수를 곱했을 때 큰 수가 되려면 양수인 경우는 큰 수 2개를 곱해야 큰 수가 될 수 있고, 음수인 경우는 작은 수 2개를 곱해야 큰 수가 될 수 있습니다.
• 또한, 이 수들을 더했을 때 최대의 수가 되려면 수를 낮추는 음수가 더해지는 경우를 줄여야 합니다.
• 0을 음수 쪽에 넣은 이유는 위에서 말했듯이 더했을 때 수를 낮추는 음수가 더해지는 경우를 최대한 줄여야 하는데, 0은 어떤 수와 곱하든 0이 되기 때문에 음수가 홀수 개일 때 남은 한 개의 음수를 0과 곱하여 0으로 만들어주기 위해 음수 쪽에 넣습니다.
• 그렇기 때문에 양수인 수와 그렇지 않은 수로 각각 나눠 저장한 다음, 양수가 들어있는 배열은 내림차순으로, 그렇지 않은 수가 들어있는 배열은 오름차순으로 정렬을 한 다음 각 배열별로 앞에서 2개씩 묶어가면서 곱해서 나온 수를 더해나갑니다.
• 양수를 곱할 때는 묶은 2개의 수 중 1이 있는지 확인하고 1인 경우는 곱하지 않고 각각 더해줍니다.
  • 예를 들어, 1이 두 개가 있을 경우, 이 두 개를 곱하여 1 * 1 = 1을 더하는 것보다 각각 수에 더해주면 2를 더하는 것과 마찬가지이기 때문에 곱한 경우보다 더 큰 수로 더할 수 있습니다.
  • 또한, 2개의 수가 1과 2인 경우, 이 두 개를 곱해서 1 * 2 = 2를 더하는 것보다 각각 수에 더해주면 3을 더하는 것과 마찬가지이기 떄문에 이 경우 또한 곱한 경우보다 더 큰 수로 더할 수 있습니다.