백준 1744번 수 묶기 - C++ 풀이

---

 

1. 양수는 양수끼리 묶고, 음수는 음수끼리 묶는다.
2. 1번 과정을 수행할 때는 수들을 정렬한 뒤, 절댓값이 큰 수부터 차례로 두 개씩 묶는 것이 최선이다.
3. n+1 > n*1이므로 1은 항상 묶지 않고, 0은 음수랑만 묶는다.

 

1. 양수는 양수끼리 묶고, 음수는 음수끼리 묶는다.

 양수와 음수를 묶으면 음수가 되어 묶지 않고 그냥 더하는 것보다 합이 더 작아진다. 따라서 양수는 양수끼리, 음수는 음수끼리만 묶도록 한다.

 

2. 1번 과정을 수행할 때는 수들을 정렬한 뒤, 절댓값이 큰 수부터 차례로 두 개씩 묶는 것이 최선이다.

 이때 합이 최대가 되려면 절댓값이 큰 수부터 차례로 묶어야 한다. 만약 숫자가 홀수개라 마지막 수가 남는다면 그냥 더해준다.

 

3. n+1 > n*1이므로 1은 항상 묶지 않고, 0은 음수랑만 묶는다.

 1과 0은 예외적으로 처리해주어야 한다. 1의 경우, n+1 > n*1이므로 항상 묶지 않아야 한다. 0의 경우 양수와 묶으면 합이 더 작아지므로 음수와만 묶도록 한다. 1번 과정을 수행할 때 남는 음수가 있다면 그것과 묶어주면 된다.

반응형

---

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

using namespace std;

typedef long long ll;

int N;
int one_cnt;
vector<ll> positives, negatives;

ll optimize(const vector<ll>& nums) {
    ll sum = 0;
    int n = nums.size();
    
    for (int i=0; i<n; i+=2) {
        if (i == n-1) sum += nums[i];
        else sum += nums[i] * nums[i+1];
    }
    
    return sum;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        ll temp;
        cin >> temp;
        if (temp == 1) one_cnt++;
        else if (temp > 0) positives.push_back(temp);
        else negatives.push_back(temp);
    }
    
    sort(positives.begin(), positives.end(), greater<ll>());
    sort(negatives.begin(), negatives.end());
    
    ll ans = optimize(positives) + optimize(negatives) + one_cnt;
    
    cout << ans;
    
    return 0;
}