[C++/백준] 1744번: 수 묶기

문제 링크

1744번: 수 묶기

 

풀이

그리디 문제
아이디어는 양수는 양수끼리 절댓값이 큰 것끼리 묶고, 음수는 음수끼리 절댓값이 큰 것끼리 묶는다.

1. 값을 입력받으며 양수이면 plus 벡터에 넣고, 음수면 minus 벡터에 넣는다.
2. plus는 내림차순 정렬, minus는 오름차순 정렬한다.
3. greedy함수를 통해 각 벡터의 최댓값을 구해 더해준다.
   1. 2번 과정을 통해 각 벡터는 절댓값이 큰 순서대로 내림차순 정렬 되어 있을텐데, 처음부터 묶어주거나 묶지 않거나를 선택해준다.
   2. 선택은 현재 숫자와 다음 숫자의 곱이 합보다 클 경우에 묶어준다. 묶어줄 경우 인덱스는 +2를 해줘야 중복해서 묶지 않게 된다.
   3. 묶지 않을 경우 인덱스를 +1 해줘서 그 다음 숫자와 묶일 수 있는지 확인하도록 한다.
4. 그렇게 구한 양수와 음수 벡터의 greedy값을 더해주어 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int greedy(vector<int> &arr)
{
    int answer = 0;
    for (int i = 0; i < arr.size();)
    {
        if (i == arr.size() - 1)
        {
            answer += arr[i];
            break;
        }

        int cur = arr[i];
        int next = arr[i + 1];
        if (cur * next > cur + next)
        {
            answer += cur * next;
            i += 2;
        }
        else
        {
            answer += cur;
            i++;
        }
    }
    return answer;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> plus;
    vector<int> minus;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        if (tmp > 0) plus.push_back(tmp);
        else minus.push_back(tmp);
    }
    sort(plus.begin(), plus.end(), greater<int>());
    sort(minus.begin(), minus.end());

    cout << greedy(plus) + greedy(minus);
}