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

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

basic-algo-lecture/workbook/0x0F.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0F.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	while (t-- > 0) {
		int n, m; // a, b 의 수
		cin >> n >> m;

		vector<int> a(n);
		for (int i = 0; i < n; i++)
			cin >> a[i];

		vector<int> b(m);
		for (int i = 0; i < m; i++)
			cin >> b[i];

		sort(a.begin(), a.end(), greater<int>()); // 내림차순 정렬
		sort(b.begin(), b.end(), greater<int>()); // 내림차순 정렬

		int totalCnt = 0; // 쌍의 개수
		int curIdx = 0; 
		for (int i = 0; i < n; i++) {
			// a 값이 b 값보다 큰 경우는 total 에 m-curIdx 더해주기
			if (a[i] > b[curIdx]) {
				totalCnt += m - curIdx;
			}
			else {
				// a 값이 b 보다 크지 않은 경우 curIdx 값을 증가시키기
				while (curIdx != m && a[i] <= b[curIdx]) {
					curIdx++;
				}

				if (curIdx == m) break; // 종료
				totalCnt += m - curIdx;
			}
		}

		cout << totalCnt << "\n"; // 정답 출력
	}


	return 0;
}

 

a, b 정렬을 내림차순 정렬 해줬다. 내림차순 정렬하는 이유는 다음과 같다.

 

일단 a 배열을 내림차순 정렬해서 a 배열의 이전 요소 값의 쌍의 개수가 다음 요소 값의 쌍의 개수보다 작을 수 없는 성질을 이용하려고 했다.

 

a 값이 b 값보다 큰 경우에는 total 에 가능한 쌍의 개수를 더해주도록 했다. m - curIdx 의 값이 현재 가능한 쌍의 개수이다. 그렇지 않은 경우에는 a 값이 b 값보다 커질 때까지 while 문을 돌린다. 만약 curIdx 의 값이 m 에 도달했으면 그냥 종료하도록 했고 그렇지 않으면 totalCnt 의 값을 갱신한 후 다음 a 요소를 보도록 했다.

 

그리고 마지막에서 totalCnt 를 출력하면 된다.