[백준] 1744번 : 수 묶기

문제

 

 

접근 방식

주어진 수열에서 순서 상관 없이 수들을 더하거나 둘을 묶어서 곱하여

가장 큰 값을 얻기 위해서는 빼야 할 때는 가능한 가장 작은 수를

더해줄 때는 가장 큰 수를 더해줘야 한다.

 

두 수를 곱하는 경우를 생각해보면

음수 * 음수 = 양수
음수 * 0 = 0
양수 * 양수 = 양수

 

위와 같이 세 가지 경우가 있고

 

두 수를 더하는 경우를 생각해보면

양수 * 1 < 양수 + 1
양수 * 0 < 양수 + 0

 

위와 같은 경우가 있다.

 

좀 더 간단하게 정리해보면 아래와 같다.

// 음수로 만들 수 있는 최적의 해
음수 * 0이하의 수

// 양수로 만들 수 있는 최적의 해
양수 * 양수
양수 + 1

 

양수는 0과 곱하거나 더하는 경우에는 어떤 이득도 볼 수 없기 때문에

0은 위와 같이 음수와 처리해주는 것이 좋다.

 

수열을 입력 받을 때 0이하의 수가 등장할 때마다

따로 변수에 카운팅을 해준 후에

수열을 오름차순으로 정렬하면

0번 인덱스 부터 카운팅한 만큼까지가 0이하의 수에 해당하고

이후의 인덱스들은 모두 양수라는 것을 알 수 있다.

-3
-2
-1

 

위와 같은 수열이 주어졌을 때를 생각해보면

-3과 -2를 곱하여 6을 만들고 -1을 빼서 5를 얻는 경우가 최적의 해이고

-2
-1

 

위와 같은 경우는 둘이 그대로 곱해 2를 얻는 경우가 최적의 해인데

여기서 알 수 있는 것이 0이하의 개수가 홀수면

마지막 인덱스를 제외한 값들은 서로 곱하고 마지막만 빼주면 되고

개수가 짝수면 모두 서로 곱해주면 된다.

 

양수의 경우는 반대로 개수가 홀수면

첫 인덱스 값을 더해주고 나머지 값들을 서로 곱해주고

짝수면 모두 서로 곱해주면 된다.

 

이제 정리한 내용들을 토대로

0번 부터 COUNT - 1번 인덱스 까지의 음수들을 처리하는 부분과

COUNT번 부터 N - 1번 까지의 양수들을 처리하는 부분을 계산해주면 된다.

 

풀이

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 count = 0;
		int[] seq = new int[n];

		for (int i = 0; i < n; i++) {
			int x = Integer.parseInt(br.readLine());
			seq[i] = x;
			if (x <= 0) count++;
		}

		Arrays.sort(seq);

		long prev = -1001;
		long sum = 0;

		for (int i = 0; i < count; i++) {
			int cur = seq[i];

			if (i == count - 1 && count % 2 != 0) {
				sum += cur;
				continue;
			}

			if (prev < -1000) {
				prev = cur;
				continue;
			}

			sum += (prev * cur);
			prev = -1001;
		}

		prev = -1001;

		for (int i = count; i < n; i++) {
			int cur = seq[i];

			if (i == count && (n - count) % 2 != 0) {
				sum += cur;
				continue;
			}

			if (prev < -1000) {
				prev = cur;
				continue;
			}

			if (prev * cur == cur) sum += (prev + cur);
			else sum += (prev * cur);
			prev = -1001;
		}

		System.out.println(sum);
	}
}