[백준][C++] 1744: 수 묶기

문제

1744번: 수 묶기

풀이

그리디, 정렬

 

수열의 음수와 양수를 나눠서 생각한다. 음수의 경우 가장 작은 수를 둘씩 묶어야 하고, 양수의 경우 가장 큰 수를 둘씩 묶어야 한다. 추가적으로, 0이 입력된 경우도 생각해야 한다. 

1. 음수의 경우, 가장 작은 수를 둘씩 묶어야 한다. 
2. 음수의 개수가 홀수인 경우
   1. 0이 입력되었다면, 음수 중 가장 큰 음수(절댓값이 가장 작은)는 0과 묶인다. 
   2. 0이 입력되지 안않다면, 음수 중 가장 큰 음수(절댓값이 가장 작은)를 정답에 더한다.
3. 양수의 경우, 가장 큰 수를 둘씩 묶어야 한다. 
4. 묶이는 수에 1이 있다면, 묶지 않는 경우가 더 큰 수를 만들 수 있으므로, 묶지 않고 정답에 더한다. 
5. 양수의 개수가 홀수인 경우, 0과 묶지 않는 경우가 더 큰 수를 만들 수 있으므로, 묶지 않고 정답에 더한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> negative;
vector<int> positive;
bool zero;

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

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int temp;
        cin >> temp;
        
        if (temp < 0)
        {
            negative.push_back(temp);
        }
        else if (temp > 0)
        {
            positive.push_back(temp);
        }
        else
        {
            zero = true;
        }
    }

    long long answer = 0;

    // 절댓값이 가장 큰 순서대로 둘 씩 묶여야 한다. 
    // 음수의 개수가 홀수이면서, 0이 입력되었다면, 음수 중 절댓값이 가장 작은 음수는 0과 묶인다.
    sort(negative.begin(), negative.end());
    for (int i = 0; i < negative.size(); i += 2)
    {
        if (i + 1 < negative.size())
        {
            answer += negative[i] * negative[i + 1];
        }
        else if(i + 1 == negative.size())
        {
            if (zero == false)
            {
                answer += negative[i];
            }
        }
    }

    // 절댓값이 가장 큰 순서대로 둘 씩 묶여야 한다. 
    // 묶이는 수에 1이 있다면, 묶지 않는 경우가 더 큰 수를 만들 수 있으므로, 묶지 않고 더하기만 한다.
    sort(positive.begin(), positive.end(), greater<>());
    for (int i = 0; i < positive.size(); i += 2)
    {
        if (i + 1 < positive.size())
        {
            if (positive[i + 1] == 1)
            {
                answer += positive[i] + positive[i + 1];
            }
            else
            {
                answer += positive[i] * positive[i + 1];
            }
            
        }
        else if (i + 1 == positive.size())
        {
            answer += positive[i];
        }
    }

    cout << answer;

    return 0;
}