수 묶기 C++ - 백준 1744

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

그리디 문제.

문제 접근

큰 수끼리 곱하고, 1이면 곱하지 않고 더한다.

음수가 남았을때는 0이 있으면 무시하고, 0이 없으면 더한다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

void solve(){
	int n;
	ll ans=0;
	cin >> n;
	int tmp;
	priority_queue<int> ppq;
	priority_queue<int> npq;
	bool zero=false;
	for(int i=0;i<n;i++){cin >> tmp;
		if(tmp>0) ppq.push(tmp);
		else if(tmp==0) zero=true;
		else npq.push(-tmp);	
	}
	while(!ppq.empty()){
		if(ppq.size()==1){ans+=ppq.top();ppq.pop();continue;}
		if(ppq.top()==1){ans+=1;ppq.pop();continue;}
		int a=ppq.top(); ppq.pop();
		if(ppq.top()==1){ans+=a+1;ppq.pop();continue;}
		a*=ppq.top(); ppq.pop();
		ans+=a;
	}
	while(!npq.empty()){
		if(npq.size()==1){
			if(zero) break;
			ans-=npq.top(); npq.pop();
			continue;
		}
		int a=npq.top(); npq.pop(); a*=npq.top(); npq.pop();
		ans+=a;        		
	}
	cout << ans;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	solve();
}