(C++) - 백준(BOJ) 1744번 : 수 묶기

www.acmicpc.net/problem/1744

1744번: 수 묶기

정렬문제였습니다.

 

풀이방법

 1. 곱이 가장 크도록 묶는 방법을 생각해야 합니다.

 

 2. n만큼 정수를 입력받을 때 음수와 양수를 따로 vector에 저장해줍니다. 양수는 0을 포함하면 안됩니다. 왜냐하면 음수에서 -1이라는 수와 0이 남은 경우 0과 곱해서 음수가 더해지는 것을 막을 수 있기 때문입니다. 반대로 양수배열에서 0을 곱해서 얻을 수 있는 이익이 없습니다. 따라서 0이 들어온다면 음수 vector에 넣어줍니다.

 

 3. 음수, 양수 vector minusNum, plusNum 변수모두 오름차순으로 정렬해줍니다. 

 

 4. plusNum의 끝부터 수를 묶고 더해줍니다. 2*1보다는 2+1이 크기 때문에 두 수의 곱과 합 중 큰 값을 ans에 더해줍니다. 2개씩 수를 확인한뒤 건너뛰므로 1개가 남았을 경우를 고려해줍니다.

 

 5. minusNum은 -7, -5, -3 ... 이런식으로 정렬되므로 처음부터 확인해서 두 개씩 묶어줍니다. -7 * -5 = 35이기 때문에 가장 작은 수 부터 묶어줍니다. 이 때는 무조건 곱한것이 합보다 이득이므로 두 수의 합을 볼 필요 없이 곱만 해주고 수를 묶은 결과 값을 ans에 더해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
vector <int> minusNum;
vector <int> plusNum;
int n, ans;
int main(){
    cin >> n;
    for(int i = 0, x; i < n; i++){
        cin >> x;
        if(x > 0) plusNum.push_back(x);
        else minusNum.push_back(x);
    }
    sort(plusNum.begin(),plusNum.end());
    sort(minusNum.begin(),minusNum.end());

    for(int i = plusNum.size() - 1; i >= 0; i-=2){
        int mul = 1;
        int sum = 0;
        mul *= plusNum[i];
        sum += plusNum[i];
        if(i - 1 >= 0) mul *= plusNum[i-1], sum += plusNum[i-1];
        ans += max(mul,sum);
    }

    for(int i = 0; i < minusNum.size(); i+=2){
        int mul = 1;
        mul *= minusNum[i];
        if(i + 1 < minusNum.size()) mul *= minusNum[i+1];
        ans += mul;
    }
    cout << ans << '\n';
}