7453번 - 합이 0인 네 정수

// https://www.acmicpc.net/problem/7453
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    vector<int> a;
    vector<int> b;
    vector<int> c;
    vector<int> d;

    cin >> n;

    int temp;
    for(int i = 0; i < n; i++){
        cin >> temp;
        a.push_back(temp);   
        cin >> temp;
        b.push_back(temp);    
        cin >> temp;
        c.push_back(temp);      
        cin >> temp;
        d.push_back(temp);
    }

    vector<int> first;
    vector<int> second;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            first.push_back(a[i] + b[j]);
            second.push_back(c[i] + d[j]);
        }
    }

    sort(first.begin(), first.end());
    sort(second.begin(), second.end());
    
    long long l = 0;
    long long r = second.size() - 1;
    long long cc = 0;
    
    while(true){
        if(l >= first.size() || r < 0){
            break;
        }

        long long result = first[l] + second[r];
        if(result == 0){
            long long lc = 1;
            long long rc = 1;
            while(l + lc < first.size() && (first[l+lc] + second[r])==0){
                lc++;
            }
            while(r-rc >= 0 && (first[l] + second[r-rc])==0){
                rc++;
            }

            cc += lc * rc;
            l = l + lc;
            r = r - rc;
        }else if(result < 0){
            l++;
        }else if(result > 0){
            r--;
        }
    }

    cout << cc << "\n";

    return 0;
}

1) 2^28은 int로도 충분히 나타낸다;;; int 4byte / long long 8 byte 그래서 long long으로 할필요가 없었다.

2) rc를 빼기 처리를 했었다. 실수!!! 

3) 나눠서 구하는것 자체는 어렵지는 않은것같다.

4) 이렇게 구하는것보다 equal range함수를 써도 좋다

include #include 

하고

result = equal_range(); 

lower bound: 크거나 같으면서 가장 작은수 result.first

upper bound: 크면서 가장 작은수 result.second

 

ex) range = equal_range(second.begin(), second.end(), -num);

하고

같은것 갯수 = range.second - range.first;

 

 

 

이제 메모리 관리같은것도 고려할때가 된것 같다.