BOJ 7795 먹을 것인가 먹힐 것인가

www.acmicpc.net/problem/7795

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

 

집합 A와 B가 주어지면 A의 각 원소를 B에서 순회하면서 그 원소보다 작은 것들이 몇 개 존재하는지를 알아내는 문제다.

처음엔 투 포인터로 접근했는데 갈수록 막히는 것 같아서 이분탐색으로 해결했다.

 

• 집합 A와 B를 입력받고 두 집합을 정렬한다
• A집합의 원소를 B집합에서 순회하면서 각 원소보다 큰 원소들이 몇개 있는지 카운트한다
• cnt 변수에 더해준다

매우 간단한 접근이였다.

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

int a[20001], b[20001], tc, n, m, cnt;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> tc;
	while (tc--) {
		cin >> n >> m;
		for (int i = 0; i < n; i++) cin >> a[i];
		for (int i = 0; i < m; i++) cin >> b[i];
		sort(a, a + n);
		sort(b, b + m);

		cnt = 0;
		for (int i = 0; i < n; i++) {
			int it = lower_bound(b, b + m, a[i]) - b;
			cnt += it;
		}
		cout << cnt << '\n';
	}

	return 0;
}

 

int it = lower_bound(b, b + m, a[i]) - b;

 

이 코드를 통해 a [i]의 원소가 B집합의 몇 번째 수에 있는지 알 수 있다.

만약 a [i]보다 큰 원소가 B집합에 없다면 마지막 인덱스를 반환할 것이다.

이후에 cnt에 추가해주면 된다.