[백준/C++]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보다 큰 쌍의 개수를 출력한다.

---

Algorithm

각각의 배열을 입력받은이후 두배열을 내림차순으로 정렬한다 이후 서로 가장 큰값들 순서대로 하나씩 비교하게 되는데 만약 A의 포인터가 가르키는 값이 B의  포인터가 가르키는 값보다 크다면 B 포인터보다 뒤에 있는 B의 값들은 자동으로 다 해당하는 값이므로 남아있는 B배열의 갯수만큼 카운트를 더한다. 만약 B가 A보다 크다면 해당하는 A가 가르키는 값보다 앞에 있는 값들은 답이아니므로 비교할 필요가 없다 이를 활용하여 두 배열의 포인터중 하나가 끝이 날때까지 비교하여 각각 하나씩 확인하는 방식으로 먹히는 순서쌍의 갯수를 더하여 구하였다. 처음에는 중복하는 순서쌍은 같은 순서쌍으로 생각하여 set을 활용하여 중복제거를 하였었는데 중복하는 순서쌍도 서로 다른 순서쌍으로 갯수를 세어야 한다.

 

---

 

 

Code

#include<iostream>
#include<algorithm>
using namespace std;
int e_cnt();
int main(){
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        cout<<e_cnt()<<'\n';
    }
    return 0;
}

int e_cnt(){
    int n,m;
    cin>>n>>m;
    int cnt=0;
    int *A=new int[n];
    int *B=new int [m];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    sort(A,A+n,greater<int>());
    sort(B,B+m,greater<int>());
    int A_idx=0,B_idx=0;
    int b_cnt=m;
    while(A_idx<n&&B_idx<m){
        if(A[A_idx]>B[B_idx]){
            cnt+=b_cnt;
            A_idx++;
        }
        else{
            b_cnt--;
            B_idx++;
        }
    }
    delete[]A;
    delete[]B;
    return cnt;
}