[백준 c++] 7795 먹을 것인가 먹힐 것인가

문제

https://www.acmicpc.net/problem/7795
심해에 사는 두 종류의 생명체 A와 B의 크기가 주어진다.
A의 크기가 B보다 큰 쌍이 몇 개인지 출력하는 문제다.

풀이

이분탐색를 이용한 풀어보고 lower_bound를 이용해서도 풀어봤다.

1. 이분탐색
   a원소들을 순회하면서 a[i]가 b의 몇 번째 원소보다 큰지 찾는다.
   left= 0, right= m-1, mid = (left + right)/2
a[i] > b[mid] -> a[i]가 더 크므로 mid값을 더 올림
   a[i] <= b[mid] -> mid값 내리기

2. lower_bound
   정렬된 벡터에서 특정 인덱스를 찾는데 유용하다.

auto pos = lower_bound(b.begin(), b.end(), a[i]);
=> a[i]가 벡터 b에서 어느 위치인지 반환(= 이터레이터)

(int)(pos - b.begin());
=> 주소값이 몇번째임을 알려면 주소값의 첫번째를 빼주기

*pos
=> 해당 이터레이터(위치) 값 반환

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int t, n, m;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        vector<int> a(n), b(m);
        int res = 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());
        for (int i = 0; i < n; i++)
        {
            int lo = 0, hi = m - 1;
            while (lo <= hi)
            {
                int mid = (lo + hi) / 2;
                if (a[i] > b[mid])
                {
                    lo = mid + 1;
                }
                else
                {
                    hi = mid - 1;
                }
            }
            res += lo;
        }
        cout << res << "\n";
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int t, n, m;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        vector<int> a(n), b(m);
        int res = 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());
        for (int i = 0; i < n; i++)
        {
            auto pos = lower_bound(b.begin(), b.end(), a[i]);
            res += (int)(pos - b.begin());
        }
        cout << res << "\n";
    }
    return 0;
}