취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2036번 문제인 수열의 점수이다.
문제는 아래 링크를 확인하자.

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

1보다 큰 양수는 큰 수부터 두 개씩 차례로 곱해 더하고 음수는 작은 수부터 두 개씩 차례로 곱해 더하는 그리디한 전략으로 문제를 해결할 수 있다.

1의 경우 다른 수와 곱해 더하는 것보다 따로 더할 때 전체 합이 1 더 커진다는 점을 놓치지 말자.

또한 문제의 답이 32비트 정수 자료형의 범위를 넘어설 수 있음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;

int N;
int cnt[2];
priority_queue<int, vector<int>, greater<>> negque;
priority_queue<int> posque;

ll ans;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		if (x > 1) posque.push(x);
		else if (x < 0) negque.push(x);
		else cnt[x]++;
	}

	while (negque.size() > 1) {
		ll val1 = negque.top(); negque.pop();
		ll val2 = negque.top(); negque.pop();
		ans += val1 * val2;
	}
	while (posque.size() > 1) {
		ll val1 = posque.top(); posque.pop();
		ll val2 = posque.top(); posque.pop();
		ans += val1 * val2;
	}

	if (posque.size()) ans += posque.top();
	if (negque.size() && !cnt[0]) ans += negque.top();
	ans += cnt[1];

	cout << ans;
}