백준 1744번 : 수 묶기 (C++)

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

1744번: 수 묶기

 

 

 

 

 

 

수열을 입력을 받고 임의의 원소들을 묶어 최대 수열 합을 구하는 문제이다. 그리디 알고리즘을 이용하면 쉽게 풀 수 있다.

입력값의 범위를 보면 -10,000 보다 크고 10,000보다 작은 수이다. 즉 양수 음수 혹은 0을 입력받는데 다음과 같은 경우로 나눌수 있다

 

1. 양수, 양수

둘다 1보다 큰 수면 두 수를 묶어 곱으로 만드는 것이 더 클것이고, 1이 존재한다면 묶지 않는게 더 크다. ( x*1 < x+1)

 

2. 음수, 음수 혹은 0

무조건 두 수를 묶어 곱셈을하여 양수 or 0으로 만드는 것이 크다.

 

 

 

그러므로 1, 양수, 음수, 0일때 각각 따로 입력을 받고, 양수의 개수가 홀수면 가장 작은수를 제거후 2개씩 묶어 곱, 덧셈을 해주고, 음수는 홀수면 가장 큰수를 0과 묶을수 있는지 검사 후 제거하거나 더해주는 식으로 하면 쉽게 구할 수있다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include<cstring>
#include <cmath>
#include <set>
#include <queue>
#include <unordered_map>
#include <deque>
#include <string>

typedef long long ll;

using namespace std;

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

	int n;
	vector <ll> positive;
	vector<ll> negative;
	int zero = 0;
	ll ans = 0;
	cin >> n;
	for(int i=0; i<n; i++){
		ll a;
		cin >> a;
		if(a==1){
			ans++;
		}
		else if(a>0){
			positive.push_back(a);
		}
		else if(a<0){
			negative.push_back(a);
		}
		else{
			zero++;
		}
	}
	
	sort(positive.begin(), positive.end(), comp);
	sort(negative.begin(), negative.end());
	if(positive.size()%2==1){
		ans += positive.back();
		positive.pop_back();
	}
	if(negative.size()%2==1){
		if(zero == 0){
			ans += negative.back();
		}
		negative.pop_back();
	}


	for(int i=0; negative.size()>0 && i< negative.size(); i += 2){
		ans += negative[i]*negative[i+1];
	}
	for(int i=0; positive.size()>0 && i<positive.size(); i += 2){
		ans += positive[i]*positive[i+1];
	}


	
	cout << ans;
}