[C++] BAEKJOON 1744 수 묶기

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

1744번: 수 묶기

그리디 알고리즘 을 이용해서 문제를 해결하였습니다.

합이 최대가 되기 위해서는 절대값이 큰 수끼리 묶어주어야 합니다. 양수에 대해서는 큰 수 끼리, 음수에 대해서는 작은 수끼리 우선적으로 곱해줍니다. 양수와 음수에 대해서 따로 받아 정렬을 한 후 두 개씩 곱해주며 더해주었습니다.

구현도 구현이지만 예외사항들을 처리해주는게 까다로웠습니다.

• 1 이 2개 이상인 경우

  1 이 2개 이상인 경우 위와 같은 알고리즘을 적용할 시 1과 1을 곱해서 더해주게 됩니다. 그러면 따로 더해주는 것 보다 오히려 작게 되므로 1은 따로 세주어서 1의 개수 만큼 더해줍니다.

• 0 이 존재하고 음수가 홀수 개인 경우

  음수가 홀수개라면 2개씩 짝을 짓고 하나가 남게 됩니다. 이 때 0이 존재한다면 0을 곱해서 음수를 없애주도록 합니다.

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

using namespace std;

int compare(int a, int b){
    if (a>b) return true;
    else return false;
}

int main(int argc, const char * argv[]) {
    
    vector <int> plus;
    vector <int> minus;
    
    int N;
    cin >> N;
    
    int answer = 0;
    int zeroNum = 0;
    int oneNum = 0;
    
    for (int i=0;i<N;i++){
        int input;
        cin >> input;
        if (input == 1) oneNum++;
        else if (input == 0) zeroNum++;
        else if (input > 0) plus.push_back(input);
        else minus.push_back(input);
    }
    // 내림차순
    sort(plus.begin(), plus.end(), compare);
  	// 오름차순
    sort(minus.begin(), minus.end());
    
    answer += oneNum;
    
    plus.push_back(1);
    minus.push_back(1);
    
    for (int i=0;i<plus.size()-1;i+=2){
        answer += plus[i] * plus[i+1];
    }
    for (int i=0;i<minus.size()-1;i+=2){
        answer += minus[i] * minus[i+1];
    }
    // minus가 홀수 개 이고 0이 있을 때 하나를 0이랑 곱해 상쇄
    if (minus.size()%2==0 && zeroNum >= 1){
        answer -= minus[minus.size()-2];
    }
    
    cout << answer << "\n";

    return 0;
}