[백준 7795] 먹을 것인가 먹힐 것인가

문제

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

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

 

 

문제 분석 

두개의 배열이 들어오고, 한쪽을 A, 다른 한쪽을 B라고 생각한다. 

 

A의 값을 하나하나 돌며 B의 값보다 크다면 선이 이어진다. 

 

이렇게 이어진 선이 몇가지인지 출력하는 문제이다. 

 

 

알고리즘 설계

전체적으로 몇번 회전할지, A의 값 회전, B의 값 회전, 안에서 입력 받을 값, 출력값을 담을 정수형 변수 하나를 선언한다. 

 

이후 전체적으로 몇번 회전할지 입력 받고 회전시켜준다. 

 

안에서 int를 담은 변수 두개를 만들어준다. 

 

A와 B 각각 몇번 회전할지 입력 받고 각각 vector에 넣어준다. 

 

두 vector모두 정렬 시켜주고, A의 값을 반복문을 돌려 하나하나 뺴준 후 B vector에 뺸 값을 lower_bounce한 값을 정답으로 출력할 변수에 담아준다. 

 

이후 모두 돌았다면 출력한다. 

 

 

유의점 

이분 탐색에 대한 이해도가 필요하다.

 

 

코드 

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

using namespace std;

int main()
{
	int loop, loop1, loop2, input, answer;
	cin >> loop;

	while (loop--)
	{
		cin >> loop1 >> loop2;
		vector<int> vec1, vec2;
		answer = 0;
		while (loop1--)
		{
			cin >> input;
			vec1.push_back(input);
		}

		while (loop2--)
		{
			cin >> input;
			vec2.push_back(input);
		}

		sort(vec1.begin(), vec1.end());
		sort(vec2.begin(), vec2.end());


		for (auto i : vec1)
			answer += lower_bound(vec2.begin(), vec2.end(), i) - vec2.begin();
		
		cout << answer << '\n';
	}
}