[BOJ/백준] 7453 C++ 합이 0인 네 정수

오늘 풀어볼 문제는 백준 7453번 합이 0인 네 정수 입니다!

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

7453번: 합이 0인 네 정수

 

 

이 문제를 효율적으로 풀기 위해 기본적으로 깔고 가야 하는 알고리즘? 최적화 방식? 은 Meet In The Middle = 중간에서 만나기 입니다! 번역하니까 열라 하찮은 느낌이네요...ㅋㅋㅋㅋ

 

굉장히 매력적인 방법이니 한 번 집중해서 뜯어보시길 권유드립니다! 

일단 이름에 걸맞게 구현 방식이 굉장히 직관적입니다... 

그냥 한 줄로 설명하자면,

그냥 머리로 박는 like 브루트포스 방식으로 풀면 시간 초과가 발생하기 때문에, 절반으로 나눠서 시간복잡도를 줄여보자~! 는 겁니다!

 

이 문제를 그냥 뇌 빼고 풀어보면 당연하게도 O((N^4))이라는 말도 안 되는 시간 복잡도가 발생합니다... 주어진 시간은 12초, 러프하게 약 1억 번의 연산 당 1초의 시간이 소요된다고 가정하고 풀면, 최악의 경우 N이 4000일 때, 4000^4번의 연산은 약 2,560,000 * 1억이라는 말도 안 되는 연산 수가 발생하므로, 2,560,000초가... 발생... 합니다... 그냥 대강 생각해 봐도 말도 안 되는 것이 느껴지니, 중간에서 만나기를 알아보고 적용해 봅시다!

 

이 문제에서 배열은 총 4개 a, b, c, d가 주어집니다.

여기서 만약 a와 b 배열을 그대로 내버려두고, c와 d 배열에 저장된 정수들을 각각 대응시켜 더한 값을 어떤 e라는 새로운 배열에 오름차순으로 정렬하여 저장해 놓은 후에 a와 b 배열에 저장된 정수들을 반복문을 통해 각각 대응시켜 더한 값을 X라고 하고, e배열에 -X가 저장되어 있는지 확인한다면 과연 시간 복잡도는 어떻게 될까요??

 

(1) c와 d 배열에 저장된 정수들을 각각 대응시켜 더한 값들을 새로운 배열 e에 삽입하기-> O((N^2))

(2) e를 정렬하기 -> O(((N^2)*log(N^2)))

(3) a와 b 배열에 저장된 정수들을 반복문을 돌려서 각각 대응시켜 더한 값을 X라고 하고, e배열에 -X가 몇 개 저장되어 있는지 이분 탐색을 2번 사용하여 확인 -> O(((N^2)*log(N^2)*2))

 

이렇게 보면 알 수 있듯이, 중간에서 만나기를 사용하면, O((N^4)) -> O((N^2)*log(N))이 되는 엄청난 일이 발생합니다... 엄청나지 않나요?

전 사실 이런 비슷한 생각을 추상적으로 했었는데 어떻게 할지 가닥이 안 잡혀서 잊고 지내다가 이걸 보고 화들짝 했습니다... 이렇게 하찮은 이름으로 존재하고 있었다니... 크흠... 암튼, 또 러프하게 최악의 경우 N이 4000일 때 연산 수를 계산해보자면,

대충, (4000^2)*log(4000)*2 = 16,000,000 * 12*2 = 약 3억 8천4백만 번의 연산이 발생함을 알 수 있습니다. 그렇다면, 12초라는 시간이 주어졌으므로, 문제없이 돌아갈 수 있겠단 생각이 듭니다! 그럼 바로 구현하기 전에, 포인트를 짚고 가볼까요?

 

일단 이 문제에선 중간에서 만나기 말고도 이분 탐색을 사용해야 합니다! 이 정도 문제 풀 정도라면 이분 탐색은 아실 거라 생각하니 이분 탐색에 대한 설명은 나중으로 미루고, 왜 이분 탐색을 2번 돌려야 하냐면! c와 d 배열에 저장된 정수들을 각각 대응시켜 더한 값을 어떤 e라는 새로운 배열에 -X$($a와 b 배열에 저장된 정수들을 반복문을 통해 각각 대응시켜 더한 값을 X라 할 때$)$가 많이 존재할 수 있기 때문입니다!

그래서 lower_bound 한 번, upper_bound 한 번 해서 총 2번 돌려주고, index값을 받아온 걸 토대로 upper_idx-lower_idx를 하면 -X인 총개수가 나오게 됩니다...!

 

그럼 이제 구현 코드를 아래에 남기고 퇴장하겠습니다..!

오류 혹은 보완할 점이 있다면 댓글로 남겨주세요!!

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
long long ans{0};
vector<int> v[4],cmp;

void Init(){
   cin>>N;
   for(int i=0; i<4; i++){
      v[i].resize(N+1);
   }
   for(int i=0; i<N; i++){
      for(int j=0; j<4; j++){
         cin>>v[j][i];
      }
   }
}

void Solve(){
   for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
         cmp.push_back(v[2][i]+v[3][j]);
      }
   }
   sort(cmp.begin(),cmp.end());
   for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
         int tmp = v[0][i]+v[1][j];
         int lo_idx = lower_bound(cmp.begin(),cmp.end(),-tmp)-cmp.begin();
         int up_idx = upper_bound(cmp.begin(),cmp.end(),-tmp)-cmp.begin();
         ans+=(up_idx-lo_idx);
      }
   }
   cout<<ans<<'\n';
}

int main(){
   cin.tie(nullptr)->ios_base::sync_with_stdio(false);
   Init();
   Solve();
   return 0;
}