[BOJ] 1744번 : 수 묶기

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n; 
vector<int> vp; // 0이상의 정수 저장
vector<int> vn; // 음의 정수 저장

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	for (int i = 1; i <= n; i++) {
		int x; 
		cin >> x;
		if (x >= 0) vp.push_back(x);
		else vn.push_back(x);
	}
	sort(vp.begin(), vp.end()); 
	sort(vn.begin(), vn.end(), [](int& a, int& b) {
		return a > b;
		});
	int ans = 0; 
	int idx = vn.size() -1;
	while (idx >= 0) {
		if (idx == 0) {
			if (vp.size() > 0) {
				if (vp[idx] != 0) ans += vn[idx];
			}
			else ans += vn[idx];
			idx--;
		}
		else {
			if (vn[idx] * vn[idx - 1] > vn[idx] + vn[idx - 1]) {
				ans += vn[idx] * vn[idx - 1]; 
				idx -= 2; 
			}
			else {
				ans += vn[idx]; 
				idx--;
			}
		}
	}
	idx = vp.size()-1;
	while (idx >= 0) {
		if (idx == 0) {
			ans += vp[idx];
			idx--;
		}
		else {
			if (vp[idx] * vp[idx - 1] > vp[idx] + vp[idx - 1]) {
				ans += vp[idx] * vp[idx - 1];
				idx -= 2;
			}
			else {
				ans += vp[idx];
				idx--;
			}
		}
	}
	cout << ans << '\n';
	
}

positive와 negative vector를 정의 후, 0 이상이면 positive에 담고, 음수면 negative에 담았다. 이렇게 하다 보니, 불필요한 코드를 두 번 적게 했고, 코드가 반복돼서, 함수로 빼려고 했지만, case분류 때문에 그러지 못했다. 

이와 같은 문제가 발생했던 이유는 1과 0의 분류 때문이다. 양수에 포함된 1은 양수를 곱하는 것보다 더하는 게 무조건 크게 된다. 따라서, 1이 나올 시, positive에 담지 말고, 그 즉시, ans에 추가해줘야 한다. 또한, 0은 양수와 상호작용할 시, 값을 더 적게 만드는 요인이다. 따라서, 처음부터 음수에 추가를 해서, -와 곱하는 게 낫다. 

 

3. solution 2 :

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> vp; 
vector<int> vn;
long long ans;
void multiple_sum(vector<int> v) {
	while (1 < v.size()) {
		ans += *(v.end() - 1) * *(v.end() - 2);
		v.pop_back();
		v.pop_back();
	}
	if (v.size()) {
		ans += *v.begin();
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x; 
		cin >> x; 
		if (x <= 0) vn.push_back(x);
		else if (x == 1) ans++;
		else vp.push_back(x);
	}
	sort(vp.begin(), vp.end()); 
	sort(vn.begin(), vn.end(), greater<>());
	multiple_sum(vp);
	multiple_sum(vn);
	cout << ans << '\n';
	
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x11/solutions/1744.cpp

basic-algo-lecture/0x11/solutions/1744.cpp at master · encrypted-def/basic-algo-lecture

나의 코드에서의 문제점을 깔끔하게 처리한 코드다. 여기서 특이한 점은 *  연산자를 이용해 , iterator의 값을 접근한다는 점과 sort에서 cmp함수를 greater <>()를 이용해 음수의 경우 내림차순으로 정렬한다는 점이다.