[백준] 2036번: 수열의 점수 | C++

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

2036번: 수열의 점수

 

 

틀린 이유

- 질문 답변 中 (https://www.acmicpc.net/board/view/21040)

아. 알고리듬이 맞은 거 같은데. 틀렸습니다가 뙇~ 하고 뜨면
오버플로우를 의심해 봐야 겠지요?

long long 형 변수 = long long형 변수 + (int형 변수 * int형 변수) 인데
int형 변수의 절대치가 100만까지 들어올 수 있거든요.. 100만 * 100만이면 딱 봐도 10^12인데 이건 2^31보다 크지 않나요?

 

그렇다... int로 지지고 볶아서 자료형 범위를 초과하면 오버플로우가 발생한다.

최종적으로 더해지는 변수만 long long으로 선언하면 되는 줄 알았다.

 

 

정답코드

#include<iostream>
#include<vector>
#include<algorithm>
#define fse(A,B,C) for(int i=A;i<B;i+=C) 
using namespace std;
typedef long long ll;
int N;
vector<ll> positive;
vector<ll> negative;
int zeroCnt;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N;
    fse(0,N,1) {
        int tmp;
        cin>>tmp;
        if(tmp==0) {
            zeroCnt++;
            continue;
        }
        if(tmp>0) positive.push_back(tmp);
        else negative.push_back(tmp);
    }

    sort(begin(positive),end(positive));
    sort(begin(negative),end(negative),greater<int>()); //내림차순
    ll answer=0;
    while(positive.size()>=2){
        ll fst=positive.back();
        positive.pop_back();
        ll snd=positive.back();
        positive.pop_back();

        if(snd!=1){
            answer+=fst*snd;
        }else{
            answer+=fst+snd;
        }
    }
    while(negative.size()>=2){
        ll fst=negative.back();
        negative.pop_back();
        ll snd=negative.back();
        negative.pop_back();
        
        answer+=fst*snd;
    }

    if(!positive.empty() && negative.empty()){
        answer+=positive.back();
    }
    else if(positive.empty() && !negative.empty()){
        if(zeroCnt>0) zeroCnt--;
        else answer+=negative.back();
    }
    else if(!positive.empty() && !negative.empty()){
        if(zeroCnt>0){
            zeroCnt--;
            answer+=positive.back();
        }else{
            answer+=positive.back()+negative.back();
        }
    }
    cout<<answer;
}