[백준 1744] 수 묶기

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

 

N인 수열이 주어졌을 때 두 수를 적당히 묶어 곱한 다음 서로 더해서 최댓값을 찾아내는 문제이다

 

입력되는 수의 범위가 -1000 ~ 1000이니 음수 처리를 적당히 해 주어야 한다.

 

그리디적 접근으로 양수의 경우는 연속된 큰 수부터 차례로 곱하면 항상 값이 최대가 된다. 이건 너무 당연한 사실이다

음수의 경우는 연속된 가장 작은 수이다 이것도 너무 당연한 사실이다.

그러면 이제 음수/양수로 나누면 0이 남는데 0을 음수에 넣어줘야 음수 * 0 = 0이되서 항상 모든 음수보다 크게 된다

 

양수 / 음수 및 0으로 나눠서 수를 저장 후 각 방식에 맞게 정렬한 다음 2개의 값을 비교해 서로 곱한 값과 더한 값 중 가장 큰 값을 정답에 누적한 다음 남은 수를 처리하면 된다.

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
using namespace std;
int N;
vector<int> positive, negative;
int main() {
    FASTIO
    cin >> N;
    for(int i = 0; i < N; i++) {
        int k; cin >> k;
        if(k <= 0) {
            negative.push_back(k);
        } else {
            positive.push_back(k);
        }
    }
    sort(positive.begin(), positive.end(), greater<>());
    sort(negative.begin(), negative.end());

    int sum = 0;
    int pi = 0, ni = 0;
    while(true) {
        if(ni + 2 > negative.size()) {
            break;
        }
        sum += max(negative[ni] + negative[ni + 1], negative[ni] * negative[ni + 1]);
        ni += 2;
    }
    while(true) {
        if(pi + 2 > positive.size()) {
            break;
        }
        sum += max(positive[pi] + positive[pi + 1], positive[pi] * positive[pi + 1]);
        pi += 2;
    }
    for(;ni < negative.size(); ni++) {
        sum += negative[ni];
    }
    for(;pi < positive.size(); pi++) {
        sum += positive[pi];
    }
    cout << sum;
}