[백준] 7795번 - 먹을 것인가 먹힐 것인가 (C++)

문제

심해에는 두 종류의 생명체 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보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000) 

---

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

---

예제 입력 1 복사

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

예제 출력 1 복사

7
1

---

풀이과정

[C++ Algorithm] 이분 탐색(Binary Search)

이분탐색이라는 개념자체를 접해본적이 없어서 개념을 이해하는데 오랜시간을 투자하게 되었다.

위에 있는 링크분의 글을 참조해서 이분탐색이 뭔지 개념을 잡았고 백준에 있는 문제를 풀며 어떻게 응용해서 코드를 구성해야하는지 생각을 하며 풀게되었습니다.

code

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

int		binary_search(std::vector <int>& n, int temp)
{
	int low, high, mid, num;

	num = 0;
	low = 0;
	high = n.size() - 1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (temp < n[mid])
			high = mid - 1;
		else if (temp >= n[mid])
			low = mid + 1;
	}
	num = n.size() - low;
	return num;
}

int		main(void)
{
	int t, a, b, temp, count;
	std::vector <int> n;

	std::cin >> t;
	for(int i = 0; i < t; i++) {
		std::cin >> a >> b;
		for(int j = 0; j < a; j++) {
			std::cin >> temp;
			n.push_back(temp);
		}
		std::sort(n.begin(), n.end());
		count = 0;
		for(int j = 0; j < b; j++) {
			std::cin >> temp;
			count += binary_search(n, temp);
		}
		n.clear();
		std::cout << count << "\n";
	}

	return (0);
}

---

후기

그렇게 오랜시간을 투자하지않았어도 될만한 문제인거같은데

이해하는시간과 어떻게 응용을 해야하는지 개념잡기가 너무 힘들었어서 시간이 걸려버렸다...