(C++) - 백준(BOJ) 7795번 : 먹을 것인가 먹힐 것인가

www.acmicpc.net/problem/7795

7795번: 먹을 것인가 먹힐 것인가

lower_bound를 구현해보는 혹은 사용해보는 문제였습니다.

 

풀이방법

 1. a,b를 오름차순으로 정렬합니다.

 2. 모든 a의 원소들에 대해서 이분탐색을 시행합니다. a의 원소가 b의 원소 이하가 되는 index 지점을 찾게 된다면 해당 index지점까지 생명체 a는 b생명체를 먹을 수 있습니다. 이를 다르게 표현하자면 a의 원소값의 lower_bound 지점을 b에서 찾게 된다면 그 지점을 다 더한 값이 답입니다.

 3. 답 출력

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, t;
int bs(int aElement, vector<int> &b){
    int l = 0;
    int r = b.size() - 1;
    int lowerBoundIdx = 0;
    while(l<=r){
        int mid = (l+r)/2;
        //aElement의 lower_bound index 찾기
        if(aElement > b[mid]) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

int main(){
    cin >> t;
    while(t--){
        int aCnt,bCnt,ans = 0;
        cin >> aCnt >> bCnt;
        vector <int> a(aCnt);
        vector <int> b(bCnt);

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

        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        
        for(int i = 0; i < aCnt; i++) ans += bs(a[i],b);
        cout << ans << '\n';
    }
}