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

 

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

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

 

 

이분 탐색으로 A가 먹을 수 있는 B를 구해줬다. 

A보다 크거나 같은 경우는 먹을 수 없으므로 R의 범위를 mid 앞으로 이동시켰고, A보다 작은 경우, 먹을 수 있으므로 counting을 해줬는데 여기서 주의할 것은 L의 이동이다. 그냥 이분 탐색이라고 생각하고 L = mid+1와 같이 작성하면 잘못된 값을 도출한다.

 

왜냐면 여기서 우리가 원하는 것은 A의 물고기보다 작은 B 물고기와의 쌍 모두를 찾아내야 하므로 mid 다음으로 그냥 넘어가면 안된다. 정렬된 B 물고기들 중 가운데 물고기가 나보다 작다면 그다음의 물고기들도 먹을 수 있는지 뒤로 이동해야 되는데, 이 범위를 L = L+1과 같이 하나씩 추가할 수 있도록 해주었다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 20002
using namespace std;
int t, n, m, A[MAX], B[MAX], cnt=0;

void input(){
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> A[i];
    for(int i=0; i<m; i++) cin >> B[i];
}

void binarySearch(int x){
    int l = 0, r = m-1;
    while(l <= r){ //원소가 하나만 남아도 됨
        int mid = (l+r)/2;
        if(x <= B[mid]){
            r = mid - 1;
        }else{
            cnt++;
            l = l + 1;
        }
    }//탐색 완료
}

void solution(){
    sort(B, B+m); //작아먹히는 B 정렬
    cnt = 0;
    for(int i=0; i<n; i++){
        binarySearch(A[i]);
    }
    cout << cnt << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        input();
        solution();
    }
    return 0;
}

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!