백준 7795번 먹을 것인가 먹힐 것인가

🔒[문제 url]

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

🪄전체 코드

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

int t,a,b;
vector<int> A,B;

int x;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
}


void SOLVE()
{
    while(t--)
    {
        //Input
        cin >> a >> b;
        for(int i = 0; i < a; i++) cin >> x , A.push_back(x);
        for(int i = 0; i < b; i++) cin >> x , B.push_back(x);

        //이분탐색 위해 정렬
        sort(A.begin(),A.end());

        int ans = 0;
        for(int i = 0; i < b; i++)
        {//B의 각 원소에 대해

            int left = 0 , right = a-1;

            //이분탐색 진행
            int idx = -1;
            while(left <= right)
            {
                int mid = (left + right) / 2;

                //B의 원소가 A[mid] 이상이라면, A[mid]를 키운다.
                if(A[mid] <= B[i]) idx = mid , left = mid + 1;
                else right = mid - 1;
            }

            //idx가 -1이라면(즉 A의 모든 원소가 B[i]보다 크다면) , ans += a;
            ans += (a-1) - idx;
        }

        cout << ans << '\n';
        A.clear(); B.clear();//Init
    }
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.