백준 1744번 수 묶기

🔒[문제 url]

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

🔑알고리즘

나열된 수를 묶어 합이 최대가 되게끔 하기위해서는 묶은 두 수의 값,
즉 묶은 두 수의 곱이 커야한다.

• 어떻게 묶어야하나?
  • 부호가 같고, 절댓값이 큰 수끼리 묶어야 그 값이 커진다.
    즉, 내림차순 정렬을 한 후 앞에서 묶어주면 될 것이다.
    
    
• 그러나, 무작정 묶으면 문제가 되는 경우가 있다. 따라서 묶는 규칙을 정해보자.

1. 내림차순 정렬을 한다.
2. 앞에서부터(절댓값이 큰 수부터) 두 개씩 묶는다. 이때, 부호는 같아야한다.
3. 어떤 수든 1과 곱하면 그대로이다. 따라서 합이 작아지지 않도록 1은 묶지않는다.
4. 0이 있는 경우 음수의 갯수가 홀수라면, 가장 큰 음수는 0과 곱한다.
   나머지 음수는 서로 곱하여 양수가 되게끔한다. 음수의 갯수가 짝수라면, 0은 묶지 않는다.
   
   

• 우선순위 큐에 수를 입력받고 Greedy하게 진행한다.
  양수, 0, 음수의 갯수를 세어줌으로써 규칙에 맞게 수를 묶으며 합을 구한다.

🐾부분 코드

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int num; cin >> num;
        if (num > 1) posCnt++; // Why "num > 1" ? Cuz of Rule3.
        else if (num == 0) zeroCnt++;
        else if (num != 1) negCnt++;
        q.push(num);
    }
}

<입력 및 갯수 세기 함수>
우선순위 큐에 수를 입력받는다.
규칙3에 의해 1은 묶지 않으므로, 1이상의 수만 양수로 간주한다.

// Top is 1
if (q.top() == 1)
{
    ans++;
    q.pop();
}

<가장 앞의 수가 1인 경우>
규칙3에 의해 묶지 않으므로, 바로 pop() 해준다.

// Top is 0
else if (q.top() == 0)
{
    if (negCnt % 2 == 0) q.pop();
    else
    {
        if (zeroCnt == 1)
        {// if queue's sequence is like [0 , negative num]
            q.pop();
            q.pop();
            negCnt--; // neg num popped
        }
        else
        {// sequence like [0 , 0]
            q.pop();
            zeroCnt--; // 0 popped
        }
    }

}

<가장 앞의 수가 0인 경우>
음수의 갯수가 짝수라면, 0은 묶지 않으므로 바로 pop() 해준다.
음수의 갯수가 홀수라면, 가장 큰 음수와 0을 묶어 합이 작아지지 않게끔 한다.
이때, 0이 여러개 존재할 수 있으므로 0이 하나일 때만 묶도록 구현한다.

// Top is positive num
else if (q.top() > 1)
{
    if (posCnt > 1)
    {
        int mulVal = q.top();
        q.pop();
        mulVal *= q.top();
        q.pop();
        posCnt -= 2; // positive num popped
        ans += mulVal;
    }
    else // if there's only one positive num
    {
        ans += q.top();
        q.pop();
        posCnt--; // positive num popped
    }
}

<가장 앞의 수가 양수인 경우>
양수가 2개 이상 있다면 무조건 묶는다.
하나일 경우, 묶지않고 pop() 해준다.

// Top is negative num
else if (q.top() < 0)
{
    if (negCnt % 2 == 1)
    {
        ans += q.top();
        negCnt--;
        q.pop();
    }
    else
    {
        int mulVal = q.top();
        q.pop();
        mulVal *= q.top();
        q.pop();
        negCnt -= 2;
        ans += mulVal;
    }
}

<가장 앞의 수가 음수인 경우>
남은 음수의 갯수가 홀수인 경우, 가장 큰 음수를 합에 추가함으로써 손실을 최소화한다. 나머지 음수끼리는 묶어준다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
// 자료 구조
#include <queue>
using namespace std;

int n;
priority_queue<int> q;
int posCnt = 0, zeroCnt = 0, negCnt = 0; // Count negative nums for Rule4.

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int num; cin >> num;
        if (num > 1) posCnt++; // Why "num > 1" ? Cuz of Rule3.
        else if (num == 0) zeroCnt++;
        else if (num != 1) negCnt++;
        q.push(num);
    }
}


void SOLVE()
{
    /*
    * Rule1 : Sort descending
    * Rule2 : multiple two nums that have biggest abs.
    *         Two nums must have same SIGN.
    * Rule3 : Do not multiple 1
    * Rule4 : if the number of negative num is odd,
    *         multiple the biggest negative num with 0
    */
    
    int ans = 0;
    while (!q.empty())
    {
        // Top is 1
        if (q.top() == 1)
        {
            ans++;
            q.pop();
        }
        // Top is 0
        else if (q.top() == 0)
        {
            if (negCnt % 2 == 0) q.pop();
            else
            {
                if (zeroCnt == 1)
                {// if queue's sequence is like [0 , negative num]
                    q.pop();
                    q.pop();
                    negCnt--; // neg num popped
                }
                else
                {// sequence like [0 , 0]
                    q.pop();
                    zeroCnt--; // 0 popped
                }
            }

        }
        // Top is positive num
        else if (q.top() > 1)
        {
            if (posCnt > 1)
            {
                int mulVal = q.top();
                q.pop();
                mulVal *= q.top();
                q.pop();
                posCnt -= 2; // positive num popped
                ans += mulVal;
            }
            else // if there's only one positive num
            {
                ans += q.top();
                q.pop();
                posCnt--; // positive num popped
            }
        }
        // Top is negative num
        else if (q.top() < 0)
        {
            if (negCnt % 2 == 1)
            {
                ans += q.top();
                negCnt--;
                q.pop();
            }
            else
            {
                int mulVal = q.top();
                q.pop();
                mulVal *= q.top();
                q.pop();
                negCnt -= 2;
                ans += mulVal;
            }
        }
    }
    cout << ans;
}



int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

경우의 수만 잘 따진다면 어렵지 않게 풀 수 있는 문제였다.
만약 자신이 다양한 케이스에 대해 생각해보는게 어렵다면,
이 문제와같이 많은 조건 분기 태그를 연습해보기 바란다.