[백준] 1744 - 수 묶기

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

1744번: 수 묶기

 

그리디한 접근법이 약간 까다로웠던 문제이다.

 

두 수를 묶는 경우의 수는 다음과 같다.

1. 음수와 음수
2. 음수와 0
3. 0과 양수
4. 음수와 양수
5. 양수와 양수
   1. 1과 1이 아닌 양수
   2. 1이 아닌 양수와 1이 아닌 양수

1번과 2번의 경우 곱하기를 하는 것이 최대이다.

3번과 4번의 경우 더하기를 하는 것이 최대이다.

5-1번의 경우 더하기를 하는 것이 최대이다.

5-2번의 경우 곱하기를 하는 것이 최대이다.

 

위 규칙만 잘 이용한다면 쉽게 풀어낼 수 있다.

 

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

int main() {
	int n;
	cin >> n;
	int a[51] = { 0, };
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int ans = 0;
	
	for (int i = 1; i <= n; i++) {
		if (a[i] < 0) {
			if (i < n && a[i + 1] <= 0) {
				ans += a[i] * a[i + 1];
				i++;
			}
			else ans += a[i];
		}
		else if (a[i] == 0) {
			continue;
		}
		else {
			if (n % 2 != i % 2 && i < n && a[i] != 1) {
				ans += a[i] * a[i + 1];
				i++;
			}
			else ans += a[i];
		}
	}
	cout << ans;
}