분할정복 - 3. 팬미팅

문제 : 팬미팅 (난이도 上)

https://algospot.com/judge/problem/read/FANMEETING

분석

 

문제를 푸는 가장 간단한 방법은 문제에 나와 있는 과정 하나하나 시뮬레이션을 하는 것이다.

그러나 멤버와 팬의 수가 각각 20만에 달하는 수이기에 이렇게 풀기엔 무리이다.

 

하지만 앞서 배운 카르츠바 알고리즘을 알고 있으면 문제가 쉽게 해결된다.

2020/11/14 - [알고리즘 문제 해결 전략] - 분할 정복 - 카라츠바 알고리즘

분할 정복 - 카라츠바 알고리즘

카라츠바의 곱셈 순서가 문제에 나와 있는 그림 순으로 진행 된다는 것을 알 수 있다.

구현

int hugs(const string& members, const string& fans)
{
	int N = members.size(), M = fans.size();
	vector<int> A(N), B(M);
	for (int i = 0; i < N; i++)
	{
		A[i] = (members[i] == 'M');
	}
	for (int i = 0; i < M; i++)
	{
		B[M - i - 1] = (fans[i] == 'M');
	}
	vector<int> C = karatsuba(A, B);
	int hugAll = 0;
	//모든 맴버가 안기를 하는 경우이므로 i = N - 1 ~
	for (int i = N - 1; i < M; i++)
	{
		if (C[i] == 0) hugAll++;
	}
	return hugAll;
}

 

시간 복잡도

카라츠바 알고리즘의 시간 복잡도인 O(n^lg3) 이 나온다.