문제

BOJ 1744, 수 묶기

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 수열이 주어질 때 모든 수열을 더한 값의 최댓값을 구해야 한다. 수열에서 임의의 두 수를 묶을 수 있는데 묶인 수는 서로 더하는 게 아니라 곱해야 한다.
• 최댓값이 되려면 양수인 두 수를 묶을 때 가장 큰 수끼리 묶어야 한다. [1, 2, 3]이 있다면 [2, 3]으로 묶어야 한다. 음수의 경우에는 가장 작은 두 수를 묶으면 최대가 된다. [-1, -2, -3]이라면 [-2, -3]을 묶는다. 0이 주어진 경우에는 음수와 묶어서 음수를 0으로 만들 수 있다. 즉, 음수 중 제일 작은 것끼리 짝을 지어 묶고 홀수라면 나머지를 0이랑 묶어 0으로 만들 수 있다. 양수를 묶을 때 주의해야 할 점이 있는데, 1과 묶으면 그 수는 작아진다. [1, 9]가 있다면 묶기 전에는 10이지만 묶고 나서는 9가 된다.
• 위의 규칙을 고려하여 정수를 입력받을 때 음수, 0, 1, 양수를 나누어 받는다. 음수는 내림차순으로 양수는 오름차순으로 정렬하여 뒤에 원소부터 묶은 뒤 계산한다.

개선

코드

시간복잡도

• $O(N\times logN)$

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> pos;
vector<int> neg;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	int zero = 0;
	int one = 0;
	for (int i = 0; i < n; ++i) {
		int num;
		cin >> num;
		if (num < 0)
			neg.push_back(num);
		else if (num == 0)
			++zero;	
		else if (num == 1)
			++one;
		else 
			pos.push_back(num);
	}
	sort(neg.begin(), neg.end(), [](auto& a, auto &b) { return  a > b; });
	sort(pos.begin(), pos.end());
	int ans = 0;
	while (neg.size() > 1) {
		ans += *(neg.end() - 1) * *(neg.end() - 2);
		neg.pop_back();
		neg.pop_back();
	}
	if (neg.size()) {
		if (zero == 0)
			ans += neg[0];
	}
	while (pos.size() > 1) {
		ans += *(pos.end() - 1) * *(pos.end() - 2);
		pos.pop_back();
		pos.pop_back();
	}
	if (pos.size()) 
		ans += pos[0];
	ans += one;
	cout << ans;
}

Java

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

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 zero = 0;
        int one = 0;
        ArrayList<Integer> neg = new ArrayList<>();
        ArrayList<Integer> pos = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num < 0)
                neg.add(num);
            else if (num == 0)
                ++zero;
            else if (num == 1)
                ++one;
            else
                pos.add(num);
        }
        neg.sort((a, b) -> Integer.compare(b, a));
        pos.sort((a, b) -> Integer.compare(a, b));
        int ans = 0;
        while (neg.size() > 1) {
            ans += neg.get(neg.size() - 1) * neg.get(neg.size() - 2);
            neg.remove(neg.size() - 1);
            neg.remove(neg.size() - 1);
        }
        if (neg.size() > 0) {
            if (zero == 0)
                ans += neg.get(0);
        }
        while (pos.size() > 1) {
            ans += pos.get(pos.size() - 1) * pos.get(pos.size() - 2);
            pos.remove(pos.size() - 1);
            pos.remove(pos.size() - 1);
        }
        if (pos.size() > 0)
            ans += pos.get(0);
        ans += one;
        System.out.println(ans);
        br.close();
    }
}