[BOJ/백준 7795][C++] 먹을 것인가 먹힐 것인가

문제

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

백준 7795

 

문제 내용

A의 원소 a와 B의 원소 b가 있을 때 a>b가 될 수 있는 모든 쌍의 개수를 구하는 문제이다.

 

문제 풀이

정렬 없이 완전탐색을 할 경우 시간초과가 나게 되는 문제이다. (n, m이 20000까지 될 수 있다)

나는 A와 B를 정렬한 후, b보다 a가 크면 A의 원소 중 a보다 큰 값을 계산 없이 카운트하는 방법을 선택했다.

 

 

코드

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

void solution() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n, 0);
    vector<int> b(m, 0);

    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int cnt = 0;
    for (int i = 0; i < b.size(); i++) {
        for (int j = 0; j < a.size(); j++) {
            if (b[i] >= a[j]) { // a가 더 크지 않으면 넘어가기
                continue;
            }
            cnt += (a.size() - j); // a[j]부터 그 뒤로 남은 a의 개수 추가
            break;
        }
    }
    cout << cnt << '\n';
}

int main() {
    int test;
    cin >> test;
    while (test--) {
        solution();
    }
}