[백준] 수 묶기 1744번 (c++) 그리디, 수를 잘 나누기

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

풀이 방법

그리디 문제로 엣지 케이스를 생각하는 것이 쉽진 않았다.

아래 규칙만 잘 지켜 준다면 해결 가능하다.

1. 양수면 무조건 큰 수 끼리 곱하기

2. 만약 수가 1이면 곱하지 않고 더하기

3. 음수 끼리 곱하면 양수가 되므로 작은 수끼리 곱하기

4. 양수 또는 음수가 홀수개가 존재하면 마지막 수는 그냥 더하기

 

문제의 핵심 포인트 : 수를 잘 나누어서 저장한다 (양수, 0 이하 따라)

수를 나누어 저장해 계산을 구현하기 쉽게 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N ,ans = 0;
vector<int> p, n;  

bool cmp1(int a, int b) {
    return a > b;
}
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) { // 수를 나누어 저장하기 양수, 0이하
        int a;
        cin >> a;
        if (a > 0) p.push_back(a);
        else {
            n.push_back(a);
        }
        
    }

    sort(p.begin(), p.end(), cmp1);  
    sort(n.begin(), n.end());
    int p_size = p.size(), n_size = n.size(); 
    if (p.size()%2 != 0) { // 양수가 홀수 개 존재하는 경우
        ans += p[p_size-1]; //마지막 수 더해주기
        p_size--; // 마지막 인덱스 감소
    }
    for (int i = 0;i < p_size;i = i + 2) {
        if (p[i+1] == 1) { // 양수가 1인 경우 더해주기
            ans += p[i] + p[i+1];
        }
        else {
            ans += (p[i] * p[i+1]);
        }
        
    }

    if (n.size() % 2 != 0) { // 음수가 홀수 개 존재한다.
        ans += n[n_size-1]; // 마지막 수 더해주기
        n_size--; // 마지막 인덱스 제거
    }
    for (int i = 0;i < n_size;i = i + 2) {        
        ans += (n[i] * n[i+1]);
    }    
    
    cout << ans << endl;
    return 0;
}