[BOJ] 7795_먹을 것인가 먹힐 것인가 with cpp

# 생각

이분탐색인 uppber_bound를 통해 풀 수 있다

단, 배열이 정렬이 되어있어야 한다

// 11을 초과하는 수가 처음 등장하는 위치 출력
// 찾지 못하면 last return
vector<int> data = { 2, 7, 13 };
int index = upper_bound(data.begin(), data.end(), 11) - data.begin();
cout << index;
// index = 2

 

정렬된 A의 크기에서

입력 받은 b보다 큰 숫자가 a에서 처음 등장하는 인덱스를 빼주면

A가 B보다 큰 쌍의 개수를 구할 수 있다

ex)

{ 2, 13, 7 } -> { 2, 7, 13 }에서 {103, 11, 290, 215}보다 큰 수는

b가 11일때 2에서 처음 등장하므로

A의 크기인 3에서 인덱스 2를 빼주면 경우의 수 1개를 구할 수 있다

만족하지 않는 조건에서는 last 값인 3이 return 되므로 ans에는 계속 0이 더해진다

for (int i = 0; i < m; i++)
	{
		int b;
		cin >> b;
		int index = upper_bound(v.begin(), v.end(), b) - v.begin();
		ans += n - index;
	}

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;
// 완전 탐색
void solution1()
{
	int TC;
	cin >> TC;
	while (TC--)
	{
		int n, m;
		cin >> n >> m;
		vector<pair<int, int>> v(n + m);
		for (int i = 0; i < n; i++)
		{
			int a;
			cin >> a;
			v[i] = { a,0 };
		}
		for (int i = n; i < n + m; i++)
		{
			int b;
			cin >> b;
			v[i] = { b,1 };
		}
		sort(v.begin(), v.end());
		int cnt = 0;	// 현재까지 나온 b의 개수
		int ans = 0;
		for (int i = 0; i < n + m; i++)
		{
			if (v[i].second == 0) ans += cnt;	// A집합
			else cnt++;	// B집합
		}
		cout << ans << '\n';
	}
}
// 이분 탐색
void solution2()
{
	int TC;
	cin >> TC;
	while (TC--)
	{
		int n, m;
		cin >> n >> m;
		vector<int> v(n);
		for (int i = 0; i < n; i++) cin >> v[i];
		sort(v.begin(), v.end());
		int ans = 0;
		for (int i = 0; i < m; i++)
		{
			int b;
			cin >> b;
			// b보다 큰 숫자가 배열(A집합)에서 처음 등장하는 위치
			int index = upper_bound(v.begin(), v.end(), b) - v.begin();
			ans += n - index;
		}
		cout << ans << '\n';
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	//solution1();
	solution2();
}

 

---

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

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