1744번

1744번 - 수 묶기

수를 묶어서 최대값을 구하는 문제.

나는 양의 수, 0과 음의 수를 나누어서 vector 에 저장하였다. 양의 수는 내림차순으로, 음과 0의 수는 오름차순으로 sorting 하였다.

양의 수는 큰수끼리 곱할 수록 커지고, 음수는 작은 수끼리 곱할 수록 커지기 때문이다.

곱하다가 남는 값은 그냥 더해주는 방식으로 처리했다.

근데 처음에 예외를 찾지 못했다.

양수를 곱할 때, 둘 중 하나라도 그 수가 1이라면, 곱하기 보다는 더하는게 나을 수 있기 때문이다.

예를 들어 수열에 1 ,2 가 있다면 1*2 =2 이지만, 1+2 = 3으로 더하는 값이 더 크다.

그래서 양의 수를 곱할 때 for문 안에서 예외처리를 해서 AC를 받을 수 있었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    int N;
    long long ans = 0;
    vector<int> plusNum;
    vector<int> minusNum;
 
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
 
        if (tmp > 0)
        {
            plusNum.push_back(tmp);
        }
        else
        {
            minusNum.push_back(tmp);
        }
    }
 
    sort(minusNum.begin(), minusNum.end());
    sort(plusNum.begin(), plusNum.end());
    reverse(plusNum.begin(), plusNum.end());
 
    for (int i = 0; i < plusNum.size() ; i+=2)
    {
        if (i + 1 < plusNum.size())
        {
            if (plusNum[i] != 1 && plusNum[i + 1] != 1)
            {
                ans += plusNum[i] * plusNum[i + 1];
            }
            else
            {
                ans += (plusNum[i] + plusNum[i + 1]);
            }
        }
        else
        {
            ans += plusNum[i];
        }
    }
 
    for (int i = 0; i < minusNum.size(); i += 2)
    {
        if (i + 1 < minusNum.size())
        {
            ans += minusNum[i] * minusNum[i + 1];
        }
        else
        {
            ans += minusNum[i];
        }
    }
 
    cout << ans << endl;
 
    return 0;
}