BOJ 1744번 수 묶기

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

github : https://github.com/junho0956/Algorithm/blob/master/1744/1744/%EC%86%8C%EC%8A%A4.cpp

 

수 묶기 문제는 일정 수열이 주어졌을 때 이 수열의 합을 최대한으로 만드는 문제입니다. 

여기서는 임의의 숫자를 다른 숫자와 묶는게 가능한데 이 묶기가 * 곱하기입니다.

 

예를 들어 0 1 2 4 3 5 라는 수가 있고 이를 모두 더하면 15가 됩니다.

하지만 (4,5) (2,3) 을 묶으면(곱하면) 0 1 (2*3) (4*5) 가 되고 이를 합하면 27이 됩니다.

 

저는 이런식으로 문제를 접근했습니다.

정수가 나올 수 있는 범위는 -10000~10000 이므로 일단 음수가 나올 수 있음에 주의해야합니다.

마찬가지로 0도 나올 수 있다는거죠!

 

그럼 양수는 최대한 높은 것끼리 곱해주는게 총 합에 이득일 것이고,

음수는 최대한 작은 것 끼리 곱해주는게 총 합에 이득일 것입니다.

 

여기서 또 뭘 생각해보았냐면

 

0과 1에 주의하는 것입니다.

1보다 큰 양수는 0과 곱해지면 무조건 손해를 보고 1과 곱해져도 무조건 손해입니다.

1 2 가 있다면 1*2 를 하는 것은 손해니까요

그리고, 음수는 분명 짝을 지어서 서로 곱하는게 무조건 이득입니다.

근데, 짝을 못찾는 음수가 남을 수 있으니, 이는 0과 곱해서 그냥 0으로 만들어버리는 것입니다.

이 경우는 단 1가지밖에 존재할 수 없습니다. 음수는 남거나 안남거나 둘 중 하나니까요

 

이 정도만 고려하니 문제를 해결할 수 있었습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<pair<int,int> > v;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int N, num;
    int zero = 0;
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> num;
        v.push_back({ num, 1 });
    }
 
    sort(v.begin(), v.end());
 
    int fin_idx = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i].first >= 0) {
            fin_idx = i;
            break;
        }
        if (i + 1 <= v.size() - 1 && v[i+1].first <= 0) {
            v[i].first *= v[i + 1].first;
            v[i + 1].second = -1;
            i++;
        }
    }
 
    for (int i = v.size() - 1; i >= fin_idx; i--) {
        if (v[i].first <= 1) break;
        if (i - 1 >= fin_idx && v[i - 1].first > 1) {
            v[i].first *= v[i - 1].first;
            v[i - 1].second = -1;
            i--;
        }
    }
 
    int total = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i].second != -1) total += v[i].first;
    }
 
    cout << total;
    return 0;
}