C++ / 7795 / 먹을 것인가 먹힐 것인가 ( 이분 탐색 )

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

문제 요약

심해에는 두 종류의 생명체 A와 B가 존재합니다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있습니다.

예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있습니다.

8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성해야합니다.

문제 풀이

1. 케이스의 개수를 입력받습니다.

2. n과 m을 입력받고, A의 값을 입력받습니다.

3. A를 정렬합니다.

4. B생명체는 입력받는데 받음과 동시에 이분탐색을 합니다.

5. 이분탐색 함수에서는 입력받은 B의 값과 가장 가까운 A의 인덱스를 이분탐색으로 찾아서 전체 사이즈에서 뺀 값을 반환 합니다.

A를 정렬 했기 때문에 전체 사이즈에서 해당 인덱스를 빼주면 B의 숫자보다 큰 A의 숫자의 개수를 반환할 수 있습니다.

6. A의 같은 숫자가 있을 수 있기 때문에 upperbound함수를 통해 같은 숫자중 가장 마지막의 나온 인덱스로 계산하도록 합니다.

7. 반환된 갯수를 저장 하고 벡터 배열을 초기화 합니다.

8. 케이스를 다 돌고 나면 정답을 저장한 배열을 출력합니다.

주의할 점

같은 숫자가 여러개가 있을 수 있다는 점을 주의 해야 합니다.

이 점을 고려 하지 않을시 올바른 개수를 출력할 수 없습니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


int n, m, t, cnt = 0;
vector<int>v;
vector<int>ans;

int bs(int x)

{
	int start = 0;
	int end = v.size() - 1;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (v[mid] < x)
		{
			start = mid + 1;
		}
		else if (v[mid] > x)
		{
			end = mid - 1;
		}
		else
		{
			return v.size() - (upper_bound(v.begin(), v.end(), v[mid]) - v.begin());
		}
	}
	return v.size() - (upper_bound(v.begin(), v.end(), v[end]) - v.begin());

}
int main()
{
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cin >> n >> m;
		for (int j = 0; j < n; j++)
		{
			int a;
			cin >> a;
			v.push_back(a);
		}
		sort(v.begin(), v.end());
		for (int j = 0; j < m; j++)
		{
			int a;
			cin >> a;
			//cout << bs(a) << "\n";
			cnt += bs(a);
		}
		ans.push_back(cnt);
		cnt = 0;
		v.clear();
	}
	for (int i : ans)
	{
		cout << i << "\n";
	}
	return 0;
}

반응형

예제 1

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

결과 1