백준 2143번 두 배열의 합[C++]

1. 문제 풀이

 이진 탐색과 누적 합의 응용으로 풀이하였습니다. 처음엔 부배열의 값들이 연속적으로 이루어져 있었기에 투 포인터를 사용해야 하는 거 아닐까? 하는 의문이 생겼습니다. 그러던 중 배열의 크기가 1,000이므로 누적합 배열을 구해놓는다면 O(N^2)으로 부 배열의 모든 합을 구할 수 있다고 판단하게 되면서 이진 탐색을 사용하는 것이 적합할 것 같다는 생각을 하게 됩니다.

 A, B의 누적합 배열로 중복되지 않은 범위의 부 배열 합 값들을 모두 저장했습니다. 이를 정렬한 다음 lower_bound와 upper_bound를 사용해 경우의 수를 계산해주었습니다.

 

[ 시간복잡도 ]

$$ O(N^{2}log M^{2})$$

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int t, n, m;
int a[1005], b[1005];

int main() {
  fastio(nullptr, false);
  
  // input
  cin >> t >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    a[i] += a[i-1];
  }
  cin >> m;
  for(int i = 1; i <= m; i++){
    cin >> b[i];
    b[i] += b[i-1];
  }

  // solve
  vi A, B; // 모든 부배열의 합을 저정할 예정
  for(int i = 1; i <= n; i++){
    for(int j = 0; j < i; j++){
      A.pb(a[i] - a[j]);
    }
  }

  for(int i = 1; i <= m; i++){
    for(int j = 0; j < i; j++){
      B.pb(b[i] - b[j]);
    }
  }

  sort(all(B));

  ll ans{};
  for(auto cur : A){
    ans += upper_bound(all(B), t - cur) - lower_bound(all(B), t - cur);
  } 

  // output
  cout << ans;
}

3. 제출 결과