[백준/그리디/C++] 1744번 수 묶기

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

1744번: 수 묶기

문제풀이 방법

1. 음수와 양수를 두 벡터에 따로 담는다 (0은 곱하면 0이 되므로 음수와 함께 담는다)
2. 큰 수 끼리 곱하면 수가 더 커지기 때문에 두 벡터를 정렬한다
3. 변수 tmp1을 두고 tmp1이 빈 경우 tmp1에 수를 넣고, tmp1에 수가 들어있는 경우 곱한 값을 result 에 넣어준다 (두 벡터 모두 수행)

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

int n;
vector<int> p, m;
int result = 0;

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

    cin >> n;
    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        if(x>0) p.push_back(x); // x가 양수인 경우 벡터 p로
        else m.push_back(x); // 0이나 음수인 경우 벡터 m으로
    }
    // 두 벡터 모두 정렬한다
    sort(p.begin(), p.end());
    sort(m.begin(), m.end());

    int tmp1 = -1;
    for(int i=p.size()-1; i>=0; i--){
        if(p[i]==1){ // 1인 경우에는 곱하기보다 더하기가 더 커짐
            result += p[i];
            continue;
        }
        if(tmp1 == -1) tmp1 = p[i]; // 앞에 수가 비어있다면 넣기
        else{
            result += tmp1 * p[i]; // 앞에 수가 있는경우 곱해서 더하기
            tmp1 =-1;
        }
    }
    if(tmp1 != -1) result += tmp1; // 묶이지 않은 수가 남은 경우 더하기

    tmp1 = 1;
    for(int i=0; i<m.size(); i++){
        if(tmp1 == 1) tmp1 = m[i]; // 앞의 수가 비어있다면 넣기
        else{
            result += tmp1*m[i]; // 앞의 수가 있는 경우 곱해서 더하기
            tmp1 = 1;
        }
    }
    if(tmp1 != 1) result += tmp1; // 묶이지 않은 수가 남은 경우 더하기

    cout << result;

    return 0;
}