백준 1744 수묶기

jathazp·2021년 8월 23일

그리디 정렬

algorithm

목록 보기

51/57

문제링크

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

문제

풀이

양수와 음수를 나누어서 두 배열에 저장한다.
양수 배열에서 최대가 되기 위해서는 가장 큰 수를 두개씩 묶어가며 곱해야 한다. 즉, 1 2 3 4 5 가있다면 5 x 4 + 3 x 2 + 1 = 27 처럼 되어야 한다.
양수 배열의 길이가 짝수이고 가장 작은 수가 1인 경우는 마지막 두 수를 곱하는것보다 더하는게 값이 크므로 더해주도록 한다.
ex) 6 5 4 3 2 1 =>(6*5)+(4*3)+2+1
음수의 경우 음수끼리 곱해서 양수로 만들어 주도록 해야한다.
또, 1과 같은 원리로 최대값을 얻기 위해 절대값이 큰 음수끼리 곱해주어야 한다.
음수 배열의 길이가 홀수인 경우 가장 큰 음수 하나가 남았다면 전체 배열에서 0이 있는지 체크하고, 0이 있다면 음수*0을 통해 음수 하나를 지워준다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int n, ans,zero;
vector<int> vPlus;
vector<int> vMinus;


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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		if (temp > 0) vPlus.push_back(temp);
		else if (temp < 0) vMinus.push_back(temp);
		else zero = 1;
	}

	sort(vPlus.rbegin(), vPlus.rend());
	sort(vMinus.begin(), vMinus.end());
	
	for (int i = 0; i < vPlus.size(); i++) {
		if (i == vPlus.size() - 1) ans += vPlus[i];
		else {
			if (vPlus[i+1]!=1) {
				ans += vPlus[i] * vPlus[i + 1];
				i++;
			}
			else ans += vPlus[i];
		}
	}

	for (int i = 0; i < vMinus.size(); i++) {
		if (i == vMinus.size() - 1) {
			if (!zero) ans += vMinus[i];
		}
		else {
			ans += vMinus[i] * vMinus[i + 1];
			i++;
		}
	}
	cout << ans;
}