[백준 1744번] 수 묶기 (C++)

문제링크 : https://www.acmicpc.net/problem/1744

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;

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

    cin >> N;
    vector<int>vp, vm;

    for(int i=0; i<N; i++)
    {
        int num;
        cin >> num;
        if(num > 0) vp.push_back(num);
        else vm.push_back(num);
    }

    sort(vp.begin(), vp.end(), greater<>());
    sort(vm.begin(), vm.end());

    int result = 0;
    for(int i=0; i+1<vp.size(); i+=2) //2쌍씩 체크
    {
        if(vp[i]==1 || vp[i+1] == 1) result += vp[i] + vp[i+1];
        else result += vp[i]*vp[i+1];
    }
    if(vp.size()%2!=0) result += vp.back(); //남은 수 더해주기

    for(int i=0; i+1<vm.size(); i+=2) //음수도 동일하게 체크
    {
        result += vm[i] * vm[i+1];
    }
    if(vm.size()%2!=0) result += vm.back();

    cout << result;

    return 0;
}

 

입력받은 수가 음수도 존재하기에, 음수와 양수를 따로 벡터에 담아준다.

이를 각각 정렬을 통해 가장 큰 값을 곱하도록 배치해준다.

덧셈의 경우에는 묶는 쌍에 1이 존재하면 더하는 것이 이득이기에, 이를 주의하고 나머지 경우에만 곱해준다.

그리고 각 입력받은 음수와 양수가 홀수 일경우 남은 수가 존재하기에, 이를 체크하여 더해준다.

 

반복문에서는 쌍을 검토하므로 i+=2해주고, 조건을 i+1<vp.size()를 해야한다.

처음에는 별 생각없이 i<vp.size()-1;로 주었으나, vp.size()==1인 경우에는 반복문 조건을 통과해 실행을 하게 되는데,

입력받은 수가 1개밖에 없어 vp[0]에만 값이 있다. 하지만 값이 없는 vp[1]에도 접근하여 OutOfBounds 오류가 발생한다.