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

 

 

문제 7795번

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

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

 

이 문제는 이진탐색으로 풀었다. 일단 테스트 케이스가 몇개인지 입력받아 반복문으로 묶어준다.
vector A,B를 N,M크기만큼 만들어(배열처럼 입력받으려고) 입력받아주고, 해당 벡터들을 정렬(이진탐색을 하기위한 필수조건)한다. A의 크기인 N만큼 반복하여 N이 먹을 수 있는 숫자가 있는지 탐색한다. 여기서 while문의 조건은 start+1<end로 해주어 값이 있는 부분만 확인할 수 있게 했다. 저렇게 하면 start와 end의 바로 앞에 있을 때 반복문을 빠져나온다. 그리고 A와 B를 각각 비교하여 A가 더 크면 start를 mid로 옮겨주고, A가 더 작거나 같으면 end를 mid로 옮긴다. 그렇게 하다가 반복문을 빠져나왔을 때 해당 start값을 count에 넣어준다. 그런데 start값은 인덱스 값이기 때문에 원래 개수보다 1이 더 작다. 그러므로 만약 인덱스에 start를 넣은 B값이 A보다 작으면 하나를 더 증가시킨다. 여기서 조건문을 달아준 이유는 먹을 수 있는 개수가 없어 start가 0이 된 경우가 있기 때문이다.

 

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

int main() {
	int T, N, M;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N >> M;
		vector <int> A(N), B(M);

		for (int j = 0; j < N; j++) {
			cin >> A[j];
		}
		for (int k = 0; k < M; k++) {
			cin >> B[k];
		}
		sort(A.begin(), A.end());
		sort(B.begin(), B.end());

		int count = 0;

		for (int j = 0; j < N; j++) {
			int start = 0, end = M;
			while (start+1 < end) {
				int mid = (start + end) / 2;
				if (A[j] > B[mid]) {
					start = mid;
				}
				else {
					end = mid;
				}
			}
			count += start;
			if (A[j] > B[start]) {
				count++;	//인덱스가 0부터니까 1 더하기
			}
		}
		cout << count << '\n';
	}
	return 0;
}