C++ / 백준 / 1744 / 수 묶기

문제

 

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

1744번: 수 묶기

 

 

문제풀이

 

 음수, 0, 양수를 나눠서 생각해야 하는 문제이다.

먼저 숫자들이 있으면 절댓값이 가장 큰 숫자들끼리 곱하여 더하는 것이 가장 큰 값을 구하는 과정이다.

따라서 음수는 오름차순으로 정렬하여 두 수를 곱하고 합 변수 sum에 더한다.

 

음수 한 개와 0이 남은 경우는 곱하여 0으로 만드는 것이 더 큰 값이므로 음수와 0은 모두 음수를 저장하는 우선순위큐에 입력한다.

양수도 비슷하게 하면 된다. 대신 우선순위큐는 내림차순으로 정렬해야 한다.

주의할 점이 값이 1이 들어올 때이다.

1은 숫자와 곱하는 것보다 그대로 sum에 더하는 것이 더 큰 값을 구할 수 있으므로 1을 입력받으면 바로 sum에 더한다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0);
	cin >> N;
	vector<int>num(N, 0);
	priority_queue<int, vector<int>, greater<int>>minus;
	priority_queue<int>plus;

	int sum(0);
	for (int idx = 0; idx < N; ++idx) {
		cin >> num[idx];
		if (num[idx] <= 0) {
			minus.push(num[idx]);
		}
		else if (num[idx] == 1) {
			sum += 1;
		}
		else if (num[idx] > 0) {
			plus.push(num[idx]);
		}
	}

	int num1(0);
	while (!minus.empty()) {
		num1 = minus.top();
		minus.pop();
		if (minus.empty()) sum += num1;
		else {
			num1 *= minus.top();
			minus.pop();
			sum += num1;
		}
	}

	while (!plus.empty()) {
		num1 = plus.top();
		plus.pop();
		if (plus.empty()) sum += num1;
		else {
			num1 *= plus.top();
			plus.pop();
			sum += num1;
		}
	}

	cout << sum;
}