백준 1744번 수 묶기

문제 링크입니다: https://www.acmicpc.net/problem/1744

간단한 그리디 문제이지만 벡터를 이용하여 구현하기는 힘든 문제였습니다.

벡터에 모든 숫자를 넣고 조건문을 통해 그리디하게 접근하려다가 계속 틀려서 최근에 자주 애용하는 우선순위 큐를 이용하여 풀었습니다.

알고리즘은 아래와 같습니다.

1. 1과 곱하면은 손해이기 때문에 1은 무조건 더합니다. 따라서, 1의 개수를 더해줍니다.

2. 양수는 내림차순으로 저장하고 음수는 오름차순으로 저장해야 두 수를 곱했을 때 최대가 됩니다.

3. 무조건 두 수를 곱한다고 가정하기 때문에 우선순위 큐의 크기가 홀수일 경우 오류가 발생합니다.

i) 따라서, 양수가 저장되어있는 우선순위 큐 크기가 홀수이면 1을 넣어줘 짝이 없는 양수를 그대로 더해주게 합니다.

ii) 음수가 저장되어있는 우선순위 큐 크기가 홀수이면 입력받은 숫자 중에 0이 있었을 경우 0을 넣어줘 0을 더해주게 하고 없었다면 i)처럼 1을 넣어줘 짝이 없는 음수를 그대로 더해주게 합니다.

#include <iostream>

#include <vector>

#include <queue>

#include <functional>

#include <algorithm>

using namespace std;

 

int N;

priority_queue<int, vector<int>, greater<int>> positive;

priority_queue<int> negative;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상

        cin >> N;

 

        int one = 0, zero = 0;

        for (int i = 0; i < N; i++)

        {

                 int num;

                 cin >> num;

 

                 if (num == 1)

                         one++;

                 else if (num > 0)

                         positive.push(num);

                 else if (num == 0)

                         zero++;

                 else

                         negative.push(num);

        }

 

        //짝이 없는 양수를 위해 1을 곱해준다

        if (positive.size() % 2)

                 positive.push(1);

        //0이 존재한다면 짝이 없는 음수에 0을 곱해준다

        //0이 존재하지 않는다면 짝이 없는 음수에 1을 곱해준다

        if (negative.size() % 2)

                 zero == 0 ? negative.push(1) : negative.push(0);

        int sum = 0;

        //양수들을 합해주고

        while(!positive.empty())

        {

                 int num1 = positive.top();

                 positive.pop();

                 int num2 = positive.top();

                 positive.pop();

 

                 sum += (num1*num2);

        }

        //음수들을 합해준다

        while(!negative.empty())

        {

                 int num1 = negative.top();

                 negative.pop();

                 int num2 = negative.top();

                 negative.pop();

                

                 sum += (num1*num2);

        }

        //1들은 그냥 더해준다

        cout << sum + one << "\n";

        return 0;

}      

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~