백준 7453 : 합이 0인 네 정수

문제 링크입니다 https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

정수로 이루어진 크기가 같은 배열 A, B, C, D가 주어질 때, 'A[a] + B[b] + C[c] + D[d] = 0'인 (a, b, c, d) 쌍의 개수를 구하는 문제였습니다. 배열의 크기 N의 범위가 4000까지이기 때문에 4중 for문을 사용한 완전 탐색으로는 제한 시간 안에 해결할 수 없었습니다. 이분 탐색(Binary Search)을 이용해 문제를 해결했습니다.

 

문제 해결 절차는 다음과 같습니다.

 

[1] 입력을 받고 2중 for문을 통해 (a+b), (c+d)의 모든 경우를 각각 ab, cd 벡터에 저장합니다.

 

[2] cd 벡터만 오름차순으로 정렬합니다.

 

[3] 구하고자 하는 경우는 결국 '(a+b) + (c+d) = 0'인 경우이므로, '(a+b) = -(c+d)'를 찾는 경우와 같습니다.

→ 즉, ab 벡터의 음수값(-(a+b))을 하나씩 비교하며 오름차순으로 정렬된 cd 벡터 안에 (-(a+b))에 해당하는 값이 몇 개나 있는지 찾습니다.

→ 여러개가 들어있을 수도 있으므로 그 값의 맨 앞 인덱스를 반환하는 함수 getS, 그 값의 맨 뒤 인덱스를 반환하는 함수 getE를 각각 호출하고 반환된 값의 차이 + 1이 찾고자 하는 수의 개수가 됩니다.

 

[4] 찾고자 하는 경우를 찾을 때마다 누적하여 더해주고 정답을 가리키는 변수는 경우의 수가 int 범위를 넘어갈 수도 있기 때문에 long long ing 형으로 선언 및 출력합니다.

 

 

[소스코드 + 주석]

 

#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int MAX = 4000 + 10;
 
int a[MAX], b[MAX], c[MAX], d[MAX], n;
 
// [4] 경우의 수가 많아서 long long int로 선언해야합니다
long long int ans;
 
// (a+b)의 값을 저장할 ab 벡터, (c+d)의 값을 저장할 cd 벡터
vector <int> ab, cd;
 
// 정렬된 cd 벡터를 이분 탐색을 이용해 value 값이 있는지 판단하고
// 해당 값이 들어있는 맨 앞 인덱스(여러개가 있다면)를 반환하며
// 해당 값을 찾을 수 없다면 -1을 반환하는 함수
int getS(int value) {
    int start, end;
 
    // 내가 찾고자 하는 값이 cd 벡터의 맨 앞의 값보다
    // 크면 start에 0번 인덱스를 줍니다
    if (cd[0] < value) start = 0;
 
    // 내가 찾고자 하는 값이 cd 벡터의 맨 앞의 값보다
    // 작다면 벡터를 탐색할 필요가 없습니다
    else if (cd[0] > value) return -1;
 
    // 내가 찾고자 하는 값이 cd 벡터의 맨 앞의 값과
    // 같다면 0번 인덱스를 반환합니다
    else return 0;
 
    // 내가 찾고자 하는 값이 cd 벡터의 맨 뒤의 값보다
    // 크다면 벡터를 탐색할 필요가 없습니다
    if (cd[cd.size() - 1] < value) return -1;
 
    // 내가 찾고자 하는 값이 cd 벡터의 맨 뒤의 값보다 작다면 
    // 맨 뒤 인덱스를 end에 부여하고 같아도
    // 맨 앞 인덱스를 찾아야 하기때문에 마찬가지
    else end = cd.size() - 1;
 
    // start는 항상 value보다 작은 값을 가리키고
    // end는 크거나 같은 값을 가리킵니다
    // 그래야 맨 앞에 있는 값을 
    // 찾을 수 있습니다
    while (1) {
        int mid = (start + end) / 2; // 중간 인덱스
 
        // start 바로 다음에 end가 위치하게 되면 내가 찾는 값이 
        // end에 있을 가능성이 있다는 뜻이고 맞다면
        // end를 반환, 아니라면 -1을 반환
        if (start + 1 == end) {
            if (cd[end] == value) return end;
            else return -1;
        }
 
        // 지금 보고 있는 곳이 내가 찾을 값보다 오른쪽이면
        // end를 mid로 땡겨서 다시 탐색합니다
        if (cd[mid] >= value) end = mid;
 
        // 지금 보고 있는 곳이 내가 찾을 값보다 왼쪽이면
        // start를 mid로 땡겨서 다시 탐색합니다
        else start = mid;
    }
}
 
// 정렬된 cd 벡터를 이분 탐색을 이용해 value 값이 있는지 판단하고
// 해당 값이 들어있는 맨 뒤 인덱스(여러개가 있다면)를 반환하며
// 해당 값을 찾을 수 없다면 -1을 반환하는 함수
int getE(int value) {
    int start, end;
 
    if (cd[0] <= value) start = 0;
    else return -1;
 
    if (cd[cd.size() - 1] < value) return -1;
    else if (cd[cd.size() - 1] > value) end = cd.size() - 1;
    else return cd.size() - 1;
 
    while (1) {
        int mid = (start + end) / 2;
 
        if (start + 1 == end) {
            if (cd[start] == value) return start;
            else return -1;
        }
 
        if (cd[mid] > value) end = mid;
        else start = mid;
    }
}
 
// ab 벡터의 모든 값에 대해 cd 벡터에 해당 값이 몇 개 있는지 찾고
// 찾을때마다 ans에 누적하여 더해준 후 반환해주는 함수
long long int solve(void) {
 
    // [3] ab 벡터의 값을 하나씩 함수의 인자로 넣어줍니다
    for (int i = 0; i < ab.size(); i++) {
 
        // [3] getS 함수로 해당 수의 맨 앞 인덱스를
        //     getE 함수로 해당 수의 맨 뒤 인덱스를 받고
        int src = getS(-ab[i]), dst = getE(-ab[i]);
 
        // 둘 중 하나라도 그 숫자를 찾지 못했으면 다음 수를 찾습니다
        if (src == -1 || dst == -1) continue;
 
        // [4] 맨 뒤 인덱스 - 맨 앞 인덱스 + 1은 그 숫자의 개수가 됩니다
        ans += dst - src + 1;
    }
    return ans;
}
 
int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
 
    // [1] (a+b)의 모든 경우를 ab 벡터에
    //     (c+d)의 모든 경우를 cd 벡터에 저장합니다
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            ab.push_back(a[i] + b[j]);
            cd.push_back(c[i] + d[j]);
        }
    // [2] (c+d)의 모든 경우를 담고있는 cd 벡터만 오름차순 정렬
    sort(cd.begin(), cd.end());
 
    // [4] '%lld'로 출력합니다
    printf("%lld", solve());
    return 0;
}

 

 

[소스코드]

 

#include<algorithm>
#include<cstdio>
#include<vector>
 
using namespace std;
const int MAX = 4000 + 10;
 
int a[MAX], b[MAX], c[MAX], d[MAX], n;
long long int ans;
vector <int> ab, cd;
 
int getS(int value) {
    int start, end;
 
    if (cd[0] < value) start = 0;
    else if (cd[0] > value) return -1;
    else return 0;
 
    if (cd[cd.size() - 1] < value) return -1;
    else end = cd.size() - 1;
 
    while (1) {
        int mid = (start + end) / 2;
 
        if (start + 1 == end) {
            if (cd[end] == value) return end;
            else return -1;
        }
        if (cd[mid] >= value) end = mid;
        else start = mid;
    }
}
 
int getE(int value) {
    int start, end;
 
    if (cd[0] <= value) start = 0;
    else return -1;
 
    if (cd[cd.size() - 1] < value) return -1;
    else if (cd[cd.size() - 1] > value) end = cd.size() - 1;
    else return cd.size() - 1;
 
    while (1) {
        int mid = (start + end) / 2;
 
        if (start + 1 == end) {
            if (cd[start] == value) return start;
            else return -1;
        }
        if (cd[mid] > value) end = mid;
        else start = mid;
    }
}
long long int solve(void) {
    for (int i = 0; i < ab.size(); i++) {
        int src = getS(-ab[i]), dst = getE(-ab[i]);
 
        if (src == -1 || dst == -1) continue;
        ans += dst - src + 1;
    }
    return ans;
}
 
int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            ab.push_back(a[i] + b[j]);
            cd.push_back(c[i] + d[j]);
        }
    sort(cd.begin(), cd.end());
    printf("%lld", solve());
    return 0;
}