BOJ 2036 : 수열의 점수

• 문제 링크 : boj.kr/2036
• 난이도 : G4
• 태그 : 그리디, 정렬

2036번: 수열의 점수

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<ll> neg, pos;
    bool is_zero = false;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        if(input < 0) neg.emplace_back(input);
        else if(input > 0) pos.emplace_back(input);
        else is_zero = true;
    }
    sort(all(neg));
    sort(all(pos), greater<ll>());
    ll ans = 0;
    for(int i = 0; i < neg.size(); i += 2) {
        if(i + 1 < neg.size()) {
            ans += neg[i] * neg[i+1];
        }
        else {
            if(is_zero) {
                ans += 0;
            }
            else {
                ans += neg[i];
            }
        }
    }
    for(int i = 0; i < pos.size(); i += 2) {
        if(i + 1 < pos.size()) {
            ans += pos[i] * pos[i+1];
            if(pos[i] == 1 || pos[i+1] == 1) {
                ans += 1;
            }
        }
        else {
            ans += pos[i];
        }
    }
    cout << ans;
    return 0;
}

---

풀이

정수 $A, B, C, D (A \le B \le C \le D)$가 있을 때,

$2 \le A$라면, 가능한 점수가 가장 큰 경우는 $AB + CD$임이 명확하다.

$D \le -1$라더라도, 가능한 점수가 가장 큰 경우는 $AB + CD$임이 명확하다.

위의 관찰을 통해 음수는 음수끼리, 양수는 양수끼리 절댓값이 큰 순서대로 곱해주는 것이 최적임을 알 수 있다.

 

음수인 정수의 개수가 홀수라면, 0을 곱해 음수를 없애줄 수 있다.

양수 중 1은 곱하는 것보다 그냥 더하는 것이 최적이다.

 

첫 번째 관찰을 통해 기본적인 틀을 세우고, 위의 두 예외처리를 통해 답을 구할 수 있다.