백준 1744 : 수 묶기

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

1. 접근

• 우선 오름차순을 해서 큰수끼리 묶어주면 된다.
• 큰양수는 큰양수끼리, 큰음수는 큰음수끼리 곱하는 것이 이득이다. (음수x양수 는 안됨)
• 양수와 음수로 나눠서 접근해본다면
  => 양수 : 큰 양수끼리 곱해야 한다. 1은 곱하는 것보다 더하는 것이 이득임
  => 음수 : 큰 음수끼리 곱해야 한다. 개수가 남는다면 0과 곱하는 것이 이득
• 수를 오름차순 정렬하면, 가장 끝에 양수가 있다. 따라서, 끝부터 줄여가면서 묶어준다. 0보다 작거나같으면 종료한다.
• 음수가 나오면, 새로운 반복문으로 0번째부터 묶어준다.

2. 추가 반례

10
-5
-4
-3
-2
-1
0
1
2
3
4

정답 : 41

2. 나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int n;
	vector<int> arr;
	int input=0;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		arr.push_back(input);
	}

	sort(arr.begin(), arr.end());

	int sum = 0;
	int negativeIndex = n-1;
	int i = 0;
	for (i = n-1; i >=0; i--) { //큰 양수들끼리 묶어주기
		if (arr[i] > 0) {
			if (i > 0) {
				if (arr[i - 1] <= 1)	sum += arr[i]; //1은 더해주는게 이득
				else {
					sum += arr[i]*arr[i - 1];
					i--;
				}
			}
			else sum += arr[i];
		}
		else { //음수나 0이 나오면 종료
			break;
		}
	}
	
	negativeIndex = i+1; //반대쪽부터 여기까지 음수 반복문 돌릴거임
	for (i = 0; i < negativeIndex; i++) { //작은 음수들끼리 묶어주기
		if (i < negativeIndex - 1) {
			sum += arr[i] * arr[i + 1];
			i++;
		}
		else sum += arr[i];
	}

	cout << sum << "\n";

}

3. 다른 사람의 풀이

https://suhwanc.tistory.com/18
아예 양수와 음수 배열을 다르게 두고 각각에 대해 반복문을 쓰고,
1의 개수만 마지막에 따로 더해주는 방식을 썼다. (설명이 뭔가 웃겼음)

결론적으로 반복문을 2개 사용한다는 점에서, 효율성은 동일하다.
하지만, 묶어주는 과정을 깔끔하게 짤 수 있었다.
더 효율적인 방법인 것 같다.