1744. 수 묶기

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

1744번: 수 묶기

 

풀이

필요 알고리즘: 그리디 알고리즘

 

문제를 읽고, 어떤 두 수를 묶어서 곱해야 수열의 전체 합이 최대가 되는지 생각해 보자. 수열의 수 \(x\)가 양수, 음수, 혹은 특정한 수일 때 다른 수와 묶는 게 옳은지, 그대로 두는 게 나은지를 중점적으로 생각해 본다.

 

일단 \(x=0\)일 때를 생각해 보자. \(0\times a=0\)이므로 양수와 묶으면 최댓값에서 손해를 본다. 하지만 음수와 곱해도 0이 되므로, 음수와 0을 묶어서 최댓값의 감소를 막는 것이 가장 이상적이다.

 

다음으로 \(x=1\)일 때이다. \(1\times a=a\)로, \(a+1\)에 비하면 역시 손해를 본다. 따라서 수가 1일 경우에는 다른 수와 묶지 않는 것이 이상적이다.

 

\(x\neq0,\,x\neq1\)일 경우, 곱셈 특성상 같은 부호끼리, 절댓값이 큰 순서대로 묶는 것이 이상적이다. 양수는 양수끼리, 음수는 음수끼리 곱해야 항상 양수가 되어 최댓값을 유지할 수 있기 때문이다. 절댓값이 큰 순서대로 묶는 이유는 필자도 정확하게 증명할 순 없지만, "보다 큰 수를 보다 크게 뻥튀기해야 최대가 보장된다"라고 생각한다면 어느 정도 이해가 되지 않을까 싶다.

 

위의 생각을 종합하면 다음과 같으며, 이를 코딩으로 구현하면 된다.

• 1을 제외한 양수끼리, 그리고 음수끼리 절댓값이 큰 순서대로 둘씩 묶어서 곱한다.
• 수열에 1이 있을 경우, 묶지 않고 그대로 더한다.
• 둘씩 묶고 남은 양수가 있다면 그대로 더한다.
• 둘씩 묶고 남은 음수가 있다면, 수열에 0이 있을 경우 더하지 않는다. 그렇지 않을 경우, 그대로 더한다.

 

시간 복잡도

최대 크기가 \(N\)인 배열을 intro sort하고, 이를 배열의 처음 또는 끝부터 순차적으로 확인하므로 \(O(N\log{N}+N)=O(N(\log{N}+1))\simeq O(N\log{N})\)이다.

 

소스코드

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

int N, ans;
bool zeros;
vector<int> pos, neg;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N;
    int tmp;
    for(int i = 0; i < N; i++) {
        cin >> tmp;
        if(tmp == 0) zeros = true;
        else if(tmp == 1) ans++;
        else if(tmp > 1) pos.push_back(tmp);
        else neg.push_back(tmp);
    }
    
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
    
    for(int i = pos.size() - 1; i >= 1; i -= 2) {
        ans += (pos[i] * pos[i - 1]);
    }
    
    if(pos.size() % 2) ans += pos[0];
    
    for(int i = 1; i < neg.size(); i += 2) {
        ans += (neg[i] * neg[i - 1]);
    }
    
    if(neg.size() % 2 && !zeros) ans += neg[neg.size() - 1];
    cout << ans;
    return 0;
}