백준 7453번 합이 0인 네 정수

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

완전탐색법을 적용하여 시간 복잡도 O(N^4)으로 풀려고 하면 절대 시간 안에 풀 수 없는 문제입니다.

알고리즘은 아래와 같습니다.

1. 4개의 배열을 2개로 나눕니다. {첫 번째 배열, 두 번째 배열}, {세 번째 배열, 네 번째 배열}

2. 첫 번째 배열과 두 번째 배열의 가능한 모든 합은 미리 전처리 할 필요 없고 세 번째 배열과 네 번째 배열의 모든 가능한 합만 미리 전처리해두고 오름차순으로 정렬합니다.

3. 첫 번째 배열과 두 번째 배열의 모든 가능한 합을 구하고 해당 합의 부호를 바꾼 값을 갖고 있는 인덱스를 2번에서 구한 배열에서 찾아봅니다.

4. 3번에서 구한 인덱스의 합과 2번에서 구한 합의 합이 0이라면 결과에 (upper_bound - lower_bound)만큼 더해줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 4000;

 

long long arr[4][MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < 4; j++)

                         cin >> arr[j][i];

 

        vector<long long> v;

        //3번째 4번째 배열 합 전처리

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         v.push_back(arr[2][i] + arr[3][j]);

 

        sort(v.begin(), v.end());

        long long result = 0;

        for(int i=0; i<N; i++)

                 for (int j = 0; j < N; j++)

                 {

                         long long half = arr[0][i] + arr[1][j];

                         //-half에 제일 근접한 인덱스 반환

                         long long low = lower_bound(v.begin(), v.end(), -half) - v.begin();

                         long long high = upper_bound(v.begin(), v.end(), -half) - v.begin();

 

                         //합이 0이여야지 성립

                         if (-half == v[low])

                                 result += (high - low);

                 }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~