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

먼저, a라는 배열과 b라는 배열을 오름차순으로 정렬시킨다. 

그리고 a 배열의 첫번째 값과 b 배열의 첫번째 값과 비교했을 때 

a의 값이 더 클경우 b의 인덱스를 하나 증가 시켜준다. 즉, b값이 a의 값보다 같거나 커질때까지 계속해서 

증가시켜주다가 해당 반복문을 통과된다면 더 이상 잡아 먹을 수 없는 인덱스를 갖는 b의 값으로 세팅 되어 있을 것이다. 

다시 말해서 새로 세팅한 b배열의 인덱스 값이 a값이 잡아먹을수 있는 개수라고 생각하면 된다. 

이 개수를 dp라는 배열에 하나하나 저장 시켜주고 출력 할 때 dp의 모든 값을 더해주면 된다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int n; cin >> n;
	while (n--) {
		int x; int y;
		cin >> x >> y;
		vector <int> a(x);
		vector <int> b(y);
		vector <int> dp(x);
		for (int i = 0; i < x; i++)cin >> a[i];
		for (int i = 0; i < y; i++)cin >> b[i];
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());
		int bi, index, result;
		bi = index = result = 0; 
		for (int i = 0; i < a.size(); i++) {
			index = i;
			while (bi < b.size() && b[bi] < a[i]) {
				bi++;
			}			 	
			if (bi == b.size())break;
			else {
				dp[i] = bi;
			}
		}
		if (index <= a.size() - 1) {
			for (int i = index; i < a.size(); i++) {
				dp[i] = bi;
			}
		}
		for (int i = 0; i < a.size(); i++) {
			result += dp[i];
		}
		cout << result << "\n";
	}
}

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