백준 1744번 <수 묶기>

백준 알고리즘 1744번

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

1744번: 수 묶기

---

1744번

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하여라. 이때, 각 수는 다른 수와 쌍을 이뤄 서로 곱하거나 혼자 쓰여야 한다. (쌍을 이룰 때는 위치에 상관없다.) 수열의 합의 최대를 구하여라.

 

입력으로 첫 줄에 수열의 크기 N이 주어진다. 그 다음 N개의 줄에 걸쳐 수열의 각 수가 주어진다.

 

출력으로 수열의 합의 최대를 출력하여라.

---

문제 해결

음수와 0, 양수로 나눠서 생각해야 한다.

• 음수의 개수가 1인 경우
  • 0의 개수가 0인 경우 -> 해당 음수 값을 누적한다.
  • 0의 개수가 0이 아닌 경우 -> 해당 음수값이 0과 곱해져서 사라진다.
• 음수의 개수가 1이 아닌 경우
  • 음수의 개수가 홀수인 경우
    • 가장 작은 음수부터 2개씩 쌍을 이뤄 곱한다.
    • 남은 한 개는 0의 개수가 0이라면 해당 음수 값을 누적하고 그렇지 않다면 0과 곱해져서 사라진다.
  • 음수의 개수가 짝수인 경우 -> 가장 작은 음수부터 2개씩 쌍을 이뤄 곱한다.
• 양수
  • 가장 큰 양수부터 2개씩 쌍을 이뤄 곱한다.
  • 이때, 2개의 양수 중 1이 있다면 곱하지 않고 더한다. 1을 곱하면 자기 자신이 되기 때문에 곱하는 것보다 더하는 것이 더 크다.
  • 양수의 개수가 홀수라면 남은 한 개는 그냥 누적하면 된다.

---

코드

package bj1744;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] number = new int[n];
		int negative = 0;
		int zero = 0;
		for (int i = 0; i < n; i++) {
			number[i] = Integer.parseInt(br.readLine());
			if (number[i] == 0) {
				zero++;
			}
			if (number[i] < 0) {
				negative++;
			}
		}
		Arrays.sort(number);
		int sum = 0;
		if (negative == 1) {
			if (zero == 0) {
				sum += number[0];
			}
		} else {
			for (int i = 0; i < negative; i += 2) {
				int temp = 0;
				if (i + 1 < negative) {
					temp = number[i] * number[i + 1];
				} else {
					if (zero == 0) {
						temp = number[i];
					}
				}
				sum += temp;
			}
		}
		for (int i = n - 1; i >= negative + zero; i -= 2) {
			int temp = 0;
			if (i - 1 >= negative + zero) {
				if (number[i] == 1 || number[i - 1] == 1) {
					temp = number[i] + number[i - 1];
				} else {
					temp = number[i] * number[i - 1];
				}
			} else {
				temp = number[i];
			}
			sum += temp;
		}
		System.out.println(sum);
	}

}

---

결과

---