[Gold IV]
https://www.acmicpc.net/problem/1744
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에
www.acmicpc.net
풀이
발상 자체는 어렵지 않은 Greedy 문제.
그러나 자잘한 case들을 모두 처리해 줘야 해서 실수할 수 있는 부분이 많았다.
#include <algorithm>
#include <iostream>
#include <vector>
#define init cin.tie(0)->ios_base::sync_with_stdio(0);
using namespace std;
typedef long long ll;
int main() {
init;
int N;
cin >> N;
vector<int> arr;
int k;
for (int i = 0; i < N; i++) {
cin >> k;
arr.push_back(k);
}
sort(arr.begin(), arr.end());
ll result = 0;
for (int i = N - 1; i >= 0; i--) {
if (i == 0) {
result += arr[i];
continue;
}
if (arr[i] > 0 && arr[i - 1] > 0) {
if (arr[i - 1] == 1) {
result += arr[i];
continue;
}
result += arr[i] * arr[i - 1];
i--;
} else if (arr[i] > 0 && arr[i - 1] == 0) {
result += arr[i];
} else if (arr[i] > 0 && arr[i - 1] < 0) {
result += arr[i];
} else if (arr[i] == 0 && arr[i - 1] < 0) {
// 남은 음수의 개수가 짝수
if (i % 2 == 0) continue;
// 남은 음수의 개수가 홀수
i--;
} else if (arr[i] < 0 && arr[i - 1] < 0) {
// 남은 음수의 개수가 짝수
if (i % 2 == 1) {
result += arr[i] * arr[i - 1];
i--;
} else {
// 남은 음수의 개수가 홀수
result += arr[i];
}
} else {
result += arr[i];
}
}
cout << result;
}