취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24999번 문제인 Prom이다.
문제는 아래 링크를 확인하자.

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

N명의 소녀들과 M명의 소년이 있을 때, 키 차이가 K 이하인 소년과 소녀의 쌍의 가짓수를 묻는 문제이다.

소녀들의 키와 소년들의 키를 정렬한 뒤, 키가 작은 소녀서부터 그 소녀와 키가 K 이하로 차이나는 소년의 구간을 찾아 문제를 해결하자.

이 때, 각 소녀와 춤을 출 수 있는 소년의 키의 범위를 [bL,bR)로 표기한다면 소녀의 키가 단조증가할수록 bL과 bR도 단조증가한다는 점을 관찰하자.

이 성질을 이용하면 스위핑을 이용해 모든 경우의 수를 O(N+M)에 세어 문제를 해결할 수 있다.

위와 같은 스위핑을 이용하지 않더라도, 각 소녀의 키마다 소년의 키의 범위를 나타내는 bL과 bR을 binary search를 이용해 구하는 방식으로 문제를 해결할 수도 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int girls[250000], boys[250001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, K; cin >> N >> M >> K;
	for (int i = 0; i < N; i++) cin >> girls[i];
	for (int j = 0; j < M; j++) cin >> boys[j];
	boys[M] = 2000000007;

	sort(girls, girls + N);
	sort(boys, boys + M);

	ll ans = 0;
	int bL = 0, bR = 0;
	for (int i = 0; i < N; i++) {
		while (boys[bR] <= girls[i] + K) bR++;
		while (boys[bL] < girls[i] - K) bL++;
		ans += bR - bL;
	}

	cout << ans;
}