BOJ 1744 : 수 묶기

• 문제 링크 : http://boj.kr/1744
• 난이도 : G4
• 태그 : 그리디, 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    deque<int> neg, pos;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        if(input == 1) ans += 1;
        else if(input <= 0) neg.emplace_back(input);
        else if(input > 0) pos.emplace_back(input);
    }
    sort(all(neg));
    sort(all(pos), greater<int>());
    if(neg.size() % 2) neg.push_back(1);
    if(pos.size() % 2) pos.push_back(1);

    while(neg.size() >= 2) {
        int a = neg.front(); neg.pop_front();
        int b = neg.front(); neg.pop_front();
        ans += a * b;
    }
    while(pos.size() >= 2) {
        int a = pos.front(); pos.pop_front();
        int b = pos.front(); pos.pop_front();
        ans += a * b;
    }
    cout << ans;
    return 0;
}

---

풀이

입력되는 수를 세 가지로 나눈다.

• 1 : 그냥 더하는 것이 최적이다.
• 2 이상의 정수 : 큰 것끼리 곱하는 것이 최적이다.
• 0 이하의 정수 : 절댓값이 큰 것끼리 곱하는 것이 최적이다.

2 이상과 0 이하의 정수를 나누어 각각의 배열에 저장한 뒤 절댓값이 큰 것이 앞으로 오도록 정렬한다.

각각의 배열의 원소가 홀수개라면 가장 끝에 1을 추가한다.

이제 앞에서부터 쌍을 지어 더해주면 된다.