[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; }