백준 알고리즘 7795번 : 먹을 것인가 먹힐 것인가

링크

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

문제

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000)

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

예제 입력 및 출력

풀이 코드(C++)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 10001
#define MOD 1000000003
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;

int tc; // 테스트 케이스

int main(){
  fastio;
  cin >> tc;
  int a,b;
  while(tc--){
    cin >> a >> b;
    int cnt = 0;
    vector<int> A(a),B(b);
    for(int i = 0; i < a; i++) cin >> A[i];
    for(int j = 0; j < b; j++) cin >> B[j];
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    for(int i = 0; i < a; i++){
      for(int j = 0; j < b; j++){
        if(A[i] == B[j]) break;
        else if(A[i] > B[j]) cnt++;
        else continue;
      }
    }
    cout << cnt << "\n";
  }
  return 0;
}

시간초과 때문에 애를 먹었던 문제...