[백준] 7453번 : 합이 0인 네 정수 (C++)

7453번 : 합이 0인 네 정수

---

문제)

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 2^28이다.

 

 

 

출력 :

합이 0이 되는 쌍의 개수를 출력한다.

 

 

 

 

 

 

 

 

풀이)

// 7453. 합이 0인 네 정수
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<long long> vec1;
vector<long long> vec2;
vector<long long> vec3;
vector<long long> vec4;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    vec1.resize(n);
    vec2.resize(n);
    vec3.resize(n);
    vec4.resize(n);
 
    // 입력 받기
    for (int i = 0; i < n; i++)
    {
        cin >> vec1[i] >> vec2[i] >> vec3[i] >> vec4[i];
    }
 
    vector<long long> v1;
    vector<long long> v2;
 
    // vec1과 vec2, vec3와 vec4로 만들 수 있는 모든 조합을 v1, v2에 넣어준다.
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            v1.push_back(vec1[i] + vec2[j]);
            v2.push_back(vec3[i] + vec4[j]);
        }
    }
 
    // 두 배열을 오름차순으로 정렬
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
 
    // n이 최대 4000 * 4000 = 16,000,000으로 int로 가능하다.
    long long iLen = v2.size();
 
    int s = 0;
    int e = iLen - 1;
 
    long long cnt = 0;
    // 둘 중 하나가 끝에 도달할 때까지 투포인터 진행
    while (s < iLen && e >= 0)
    {
        long long _sum = v1[s] + v2[e];
 
        if (_sum == 0)
        {
            long long temp_s = 0;
            long long temp_e = 0;
 
            // 같은 수가 나올 수 있기 때문에 
            // 해당 s, e로부터 같은 수의 개수를 세어준다.
            
            // 그 이후에는 s++, e--를 동시에 진행하지 않고,
            // 둘 중 하나만 옮긴다.
 
            long long left_cnt = 0;
            for (int i = s; s < iLen; s++)
            {
                if (v1[s] != v1[i])
                {
                    temp_s = i;
                    break;
                }
                left_cnt++;
            }
 
            long long right_cnt = 0;
            for (int i = e; e >= 0; e--)
            {
                if (v2[e] != v2[i])
                {
                    temp_e = i;
                    break;
                }
                right_cnt++;
            }
 
            cnt += left_cnt * right_cnt;
 
            if (left_cnt > 0) s = temp_s;
            else if (right_cnt > 0) e = temp_e;
        }
 
        else if (_sum < 0) s++;
        else e--;
    }
 
    cout << cnt;
 
    return 0;
}
 

---

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

7453번: 합이 0인 네 정수