[백준/C++] 1744번 수 묶기

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

1744번: 수 묶기

수를 2개씩 묶거나, 더해가면서 수열의 합 중 최대 값을 찾는 문제이다.

양수를 담을 벡터 하나, 0을 담을 벡터 하나, 음수를 담을 벡터 하나 총 3개의 벡터를 활용하였다.

양수는 내림차순으로, 음수는 오름차순으로 정렬해준 뒤, 최댓값을 계산하면 된다!

먼저 양수에서는, 나의 다음 숫자가 1인 경우가 중요하다. 양수는 거의 곱하는 것이 이득인데, 1일 때는 곱하는 것보다 더하는 것이 더 이득이기 때문이므로 해당 케이스를 잘 고려해주자.

또한 양수 벡터의 길이가 1이거나, 홀수인 경우에는 짝이 맞지 않으므로 짝 지어지지 못한 수를 변수에 따로 저장해주자!

​

음수에서도 마찬가지로 곱하는 것이 이득인데, 음수의 경우에는 '항상' 곱하는 것이 이득이다!

마찬가지로 음수 벡터의 길이가 1이거나 홀수인 경우, 변수 odd_neg에 따로 저장해주자.

만약 0이 하나 이상 존재한다면 남은 음수는 무조건 0과 곱해서 없애야하므로 변수 odd_neg를 0으로 만들어준다.

그리고 누적 합과 odd_pos, odd_neg를 더해준다면 답이다! (odd_pos, odd_neg 두 변수를 0으로 선언할 때 0으로 선언했기 때문에, 길이가 짝수여도 최종값엔 영향을 주지 않는다.)

#include <bits/stdc++.h>

using namespace std;

vector<int> pos;
vector<int> zero;
vector<int> neg;
int n,sum,num,odd_pos=0,odd_neg=0;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> num;
        if (num>= 1) pos.push_back(num);
        else if (num == 0) zero.push_back(num);
        else neg.push_back(num);
    }
    sort(pos.begin(), pos.end(), greater<>());
    sort(neg.begin(), neg.end(), less<>());

    if(!pos.empty()){
        for (int i = 0; i < pos.size(); i++) {
            if(i==(pos.size()-1)){
                odd_pos = pos[i];
                //cout << "odd_pos : " << odd_pos << endl;
                break;
            }
            if (pos[i + 1] != 1) sum = sum + pos[i] * pos[++i];
            else if (pos[i + 1] == 1) sum = sum + pos[i] + pos[++i];

        }
    }
    if(!neg.empty()){
        for (int i = 0; i < neg.size(); i++) {
            if(i==(neg.size()-1)){
                odd_neg = neg[i];
                break;
            }
            sum = sum + neg[i] * neg[++i];
        }
    }
    if(!zero.empty()){
        odd_neg=0;
    }
    sum = sum + odd_pos + odd_neg;
    cout << sum;
    return 0;
}