[BOJ] C++ 1744 수 묶기 - 조건에 따라 분류하며 정렬하기

4
-1
2
1
3

answer : 6

6
0
1
2
4
3
5

answer : 27

1
-1

answer : -1

---

배열의 각 숫자를 위치에 관계없이 두 개씩 묶을 수도 있고 묶지 않을 수 있다. 그리고 원소들의 합을 구하는데, 묶은 수끼리는 곱하고 모든 수를 더해서 그 값이 최대가 되게 하면 된다.

 

우선 배열을 정렬한다. 그 후 규칙에 따라서 묶을지 말지, 어떤 수와 묶을지를 정하였다.

 

규칙 1) 음수끼리는 묶는다. 단, 작은 수 끼리 묶는다. 
규칙 2) 묶이지 못한 음수는 0과 묶을 수 있으면 묶고 아니라면 묶지 않는다.

규칙 3) 0은 음수가 아니면 묶지 않는다.

규칙 4) 1은 묶지 않는다.

규칙 5) 양수는 양수끼리 묶는다. 단, 큰 수 끼리 묶는다.

 

 이 정도 규칙을 생각했고, 이제 이 조건들을 코드로 짜면 되는데, 이 과정에서 어디부터 음수가 끝나는지, 0이 어디부터 어디까지인지 등의 정보가 필요했다. 따라서 입력받을 때 음수의 개수와 0의 수, 1의 수를 기억했다가 정렬 후 써먹을 수 있었다. 

for (int i = 0; i < N; i++)
{
    cin >> arr[i];
    if (arr[i] == 0)
        count_zero++;
    else if (arr[i] == 1)
        count_one++;
    else if (arr[i] < 0)
        count_neg++;
}
sort(arr.begin(), arr.end());

이런 식으로 입력할 때 count_zero, count_one, count_neg를 기억한 뒤 정렬하면 음수는 0 ~ count_neg - 1까지 있다. 0은 count_neg ~ count_neg + count_zero - 1까지 있다. 1은 count_neg + count_zero ~ count_neg + count_zero + count_one - 1까지 있다. 1 초과의 양수는 count_neg + count_zero + count_one ~ N - 1까지 있다. 그 뒤는 규칙을 차례로 적용시키면서 풀었다.

 

주의할 점은 규칙 1번을 놓치고 풀 수 있다는 것이다. 문제에서 제시해 준 예제들은 악랄하게도 규칙 1번을 놓치고 풀어도 모두 맞게 나온다. 

/** 정렬 1744 수 묶기 **/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int N;
    cin >> N;

    vector<int> arr(N);
    int count_zero = 0, count_neg = 0, count_one = 0, count_rem;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
        if (arr[i] == 0)
            count_zero++;
        else if (arr[i] == 1)
            count_one++;
        else if (arr[i] < 0)
            count_neg++;
    }
    sort(arr.begin(), arr.end());

    // 정렬된 배열의 음수 숫자들은 0 ~ count_neg - 1의 index까지 있다.
    // 0은 count_neg ~ count_neg + count_zero - 1의 index까지 있다.
    // 1은 count_neg + count_zero ~ count_neg + count_zero + count_one - 1의 index까지 있다.
    // 1초과의 양수는 count_neg + count_zero + count_one ~ N - 1의 index까지 있다.

    // *규칙 1) 음수는 음수끼리 묶어야한다. 작은 수 끼리 묶는게 우선이다.
    if (count_neg > 1)
    {
        for (int i = 0; i < count_neg - 1; i += 2)
        {
            arr[i] = arr[i] * arr[i + 1];
            arr[i + 1] = 0;
        }
    }
    // 묶이지 못한 음수의 수는 count_rem이다.
    // arr[count_neg - 1]은 0이 시작되는 배열의 바로 전이다. 이 수가 0이면 음수끼리 모두 묶은 것이고 아니면 음수 하나가 남은 것이다.
    if (arr[count_neg - 1] == 0)
        count_rem = 0;
    else
        count_rem = 1;

    // *규칙 2) 음수끼리 묶지 못한 수가 존재한다면 0과 묶는다.
    if (count_rem == 1 && count_zero >= 1)
        arr[count_neg - 1] = 0;

    // *규칙 3) 1은 무조건 묶지 않는다. 그리고 2이상의 양수는 모두 묶는데, 큰 수끼리 묶어야 한다.
    for (int i = N - 1; i > count_neg + count_zero + count_one; i -= 2)
    {
        arr[i] = arr[i] * arr[i - 1];
        arr[i - 1] = 0;
    }

    int res = 0;
    for (auto x : arr)
        res += x;
    cout << res;
}