백준

백준 7453 합이 0인 네 정수

콩순이냉장고 2022. 3. 7. 19:44

문제 URL : https://www.acmicpc.net/problem/7453

 

7453번: 합이 0인 네 정수

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

www.acmicpc.net

 

문제 접근법 : 4개의 배열로 A[i],B[i],C[i],D[i]를 각각 n개씩 입력받아 A+B+C+D = 0이 되는 정수의 개수를 찾는 문제 입니다. n이 4000 이니 4000^4은 시간 초과가 자명한문제니 다른방법으로 풀어야 겠죠?

 

저식을 다르게 생각해봇빈다. C와 D를 우변으로 넘기면 A+B=-(C+D)가 됩니다.

즉 A+B가 -(C+D)인 구간을 찾으면 될것같네요

처음 이문제를 봤을대 unordered_map 으로 풀어서 시간 복잡도 n^2에 풀수 있을거라 생각했는데

unordered_map이 그렇게 빠르지 않더군요 틀렸다가 나오는게 아닌 시간초과가 발생해서

 

A+B가 -(C+D)인 구간을 찾기 문제는 이분탐색이면 충분히 찾을수 있습니다. 그러나

중복값도 존재할수 있으니 UPPER_BOUND() 와 LOWER_BOUND의 차이로 충분히 그갯수를 새는것이 더빠르겠죠?

 

소스코드 : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int n;
vector<int> v[4],sumA,sumB;
void input() {
    cin >> n;
    v[0= v[1= v[2= v[3= vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> v[0][i] >> v[1][i] >> v[2][i] >> v[3][i];
    }
     
}
void solve() {
    
    long long res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sumA.push_back(v[0][i] + v[1][j]);
            sumB.push_back(-(v[2][i] + v[3][j]));
 
        }
    }
    sort(sumB.begin(), sumB.end());
    for (int i = 0; i < sumA.size(); i++) {
        int  idx = lower_bound(sumB.begin(), sumB.end(), sumA[i]) - sumB.begin();
        if (sumA[i] == sumB[idx]) {
            int diff = upper_bound(sumB.begin(), sumB.end(), sumA[i]) - sumB.begin() - idx;
            res += diff;
        }
    }    
    cout << res << "\n";
}
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r",stdin);
    input();
    solve();
}
cs

 

A+B에 대한-(C+D)를 찾는거니 sumA 벡터는 굳이 정렬을 할필요없다는점은 알아주세요

이것의 시간복잡도는 n^2log(n^2) 입니다.

 

 

 

한가지더 다른풀이가있습니다.

투포인터를 이용한 방법이죠

 

 

A+B=-(C+D)를 찾는 문제니 하나의 

두벡터가 같은 구간을 찾아 투포인터로도 찾을수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int n;
vector<int> v[4],sumA,sumB;
void input() {
    cin >> n;
    v[0= v[1= v[2= v[3= vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> v[0][i] >> v[1][i] >> v[2][i] >> v[3][i];
    }
     
}
void solve() {
    
    long long res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sumA.push_back(v[0][i] + v[1][j]);
            sumB.push_back(-(v[2][i] + v[3][j]));
        }
    }
    sort(sumA.begin(), sumA.end());
    sort(sumB.begin(), sumB.end());
    long long l1 = 0, l2 = 0;
    while (l1 < n * n && l2 < n * n) {
        if (sumA[l1] == sumB[l2]) {
            long long r1 = l1, r2 = l2;
            while (r1 < n * n && sumA[l1] == sumA[r1])
                r1++;
            while (r2 < n * n && sumB[l2] == sumB[r2])
                r2++;
            res+= (r1 - l1) * (r2 - l2);
            l1 = r1;
            l2 = r2;
        }
        else if (sumA[l1] < sumB[l2])
            l1++;
        else
            l2++;
    }
    cout << res << "\n";
}
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r",stdin);
    input();
    solve();
}
cs

 

 

궁금한점 혹은 모르는점 어떤질문이라도 댓글은 언제나 환영입니다.