BOJ - (Algospot) FANMEETING 해결 전략 (C++)

• 문제

  가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬 미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포옹을 합니다. 모든 팬들은 동시에 한 명씩 움직입니다. 아래 그림은 행사 과정의 일부를 보여줍니다. a~d는 네 명의 하이퍼시니어 멤버들이고, 0~5는 여섯 명의 팬들입니다.

  하지만 하이퍼시니어의 남성 멤버들이 남성 팬과 포옹하기가 민망하다고 여겨서, 남성 팬과는 포옹 대신 악수를 하기로 했습니다. 줄을 선 멤버들과 팬들의 성별이 각각 주어질 때 팬 미팅이 진행되는 과정에서 하이퍼시니어의 모든 멤버가 동시에 포옹을 하는 일이 몇 번이나 있는지 계산하는 프로그램을 작성하세요.

• 입력

  첫 줄에 테스트 케이스의 개수 C (C≤20)가 주어집니다. 각 테스트 케이스는 멤버들의 성별과 팬들의 성별을 각각 나타내는 두 줄의 문자열로 구성되어 있습니다. 각 문자열은 왼쪽부터 오른쪽 순서대로 각 사람들의 성별을 나타냅니다.

  M은 해당하는 사람이 남자, F는 해당하는 사람이 여자임을 나타냅니다. 멤버의 수와 팬의 수는 모두 1 이상 200,000 이하의 정수이며, 멤버의 수는 항상 팬의 수 이하입니다.

• 출력

  각 테스트 케이스마다 한 줄에 모든 멤버들이 포옹을 하는 일이 몇 번이나 있는지 출력합니다.

• 예제 입력
  4
  FFFMMM
  MMMFFF
  FFFFF
  FFFFFFFFFF
  FFFFM
  FFFFFMMMMF
  MFMFMFFFMMMFMF
  MMFFFFFMFFFMFFFFFFMFFFMFFFFMFMMFFFFFFF

• 예제 출력
  1
  6
  2
  2

해결 전략

  Divide & Conquer 범주에 들어가 있는 문제임을 알았지만, 최초 문제 해결 시도 시에는 문자열 처리 방식으로도 시간 내에 해결할 수 있지 않을까?라는 생각이 있었다. 따라서 과거 학부 자료구조 수업에서 열심히 공부했던 KMP 알고리즘을 기반으로 변형을 가해 문제 해결을 시도했지만, 아쉽게도 시간 초과를 면하지 못했다. 본질적으로 본 문제가 Matching을 체크하는 것이 아니다보니 아무리 변형을 시도해도 O(N + M)을 구현하지 못했다고 추측된다.

  따라서 해결 시도를 포기하고 도대체 이 문제를 어떻게 Divide & Conquer를 할 수 있는지 알기 위해 교재의 전략을 읽어보니, 매우 신박하게 '큰 수의 곱셈' 문제로의 전환이 이루어짐을 알 수 있었다.

F를 0, M을 1로 두고, Members와 Fans를 곱할 시, 결과 배열의 각 자리 C[i]가 1이면 모두 포옹을 한 상태이다.

  라는 원리를 파악하는 것이 매우 주요한 문제이다. 이러한 문제 변환 시각을 가질 수 있도록 앞으로도 꾸준한 연습이 필요할 것이라 느껴진다.

  한편, 이 아이디어를 떠올린다해도, 본 문제의 입력 크기를 고려하면, 곱셈 과정에서 '큰 수의 곱셈'과 관련된 알고리즘, 그 중에서도 '카라추바 알고리즘'을 떠올리지 않으면 시간 내에 해결이 불가하다. Strassen 알고리즘과 유사한 Karatsuba 알고리즘은 아이디어는 간단하지만, 그 구현 과정 자체가 상당히 복잡하고 엄밀성을 요구한다. 본 문제가 '알고리즘 문제 해결 전략 세트' 교재에서 '상 Level'에 포함되는 이유가 바로 이러한 부분에서 오지 않나 싶다. 아이디어를 떠올리는 것도 어려우며, 설사 떠올렸다 하여도 그 구현 방법을 엄밀히 기억하지 않는 이상 1시간 내의 문제 해결이 매우 어려운 유형이다.

  Karatsuba Algorithm은 익히 알려진 것처럼, 큰 수의 곱셈 상황에서, 큰 수를 배열로 처리한 다음, 수를 반으로 분할해가면서 재귀적으로 그 곱셈을 수행하는 알고리즘이다. 이때, 곱셈 연산의 수를 최소로 줄이도록 아래와 같은 수식의 변화를 꾀함이 잘 알려져 있다.

a x b = a1b110^2k + (a1b0 + a0b1)10^k + a0b0 = z2102k + z110^k + z0
z2 = a1 b1;
z0 = a0 b0;
z1 = (a0 + a1) (b0 + b1) - z0 - z2;

  (배열로 표현한) 큰 수를 반으로 가른다. 10^k 위치를 기준으로 두 배열 a1과 a0를 도입하는 것이다. 그 다음, 위와 같은 수식을 기반으로 곱셈 부분에서의 재귀호출 및 배열 표현 시의 수 덧셈과 뺄셈 과정을 수행한다.
  이때, Threshold를 적당히 지정하여, Threshold 이하 지점에서는 Naive한 곱셈을 수행한다. 이때의 Naive한 곱셈 수행 부분은, 큰 수를 다루고 있으므로 배열 표현 시 적합한 '부분곱의 합' 방식을 취한다.
  이때, 일반적으로는 Normalize, 즉, 자리수 수정 처리 과정이 필요하지만, 본 문제에서는 수가 1과 0으로만 이루어져 있어 Carry나 Borrow의 등장이 없으므로 불필요하다.

  본 알고리즘에 대한 구체적 설명과 역사는 다른 자료에서 충분히 찾을 수 있으므로 본 포스팅에선 생략한다(아래의 코드 주석에 최대한 Detail하게 설명해놓긴 했다.)

아래는 코드이다. 자세한 아이디어는 교재 내용 및 주석으로 대체한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
// Algospot - FANMEETING
using namespace std;

void normalize(vector<int>& num) {
	// 자리수 올림을 위해 존재하는 코드. 본 문제에선 사용 x. 정수가 0, 1로만 이루어지므로
	num.push_back(0);	// 자리수 올림을 위해, 수의 맨 앞에 0을 추가

	for (int i = 0; i < num.size() - 1; i++) {
		if (num[i] < 0) {		// 카라추바 알고리즘에 필요한 부분 !!
			int borrow = (abs(num[i]) + 9) / 10;
			num[i + 1] -= borrow;
			num[i] += borrow * 10;
		}
		else {		// 일반적인 곱의 합 방식 곱셈 알고리즘에 필요한 부분
			num[i + 1] += num[i] / 10;
			num[i] %= 10;
		}
	}
	while (num.size() > 1 && num.back() == 0) // 맨 앞에 0이 있으면 Truncate하자.
		num.pop_back();
}

vector<int> multiply(const vector<int> &A, const vector<int> &B) {	
	// Naive한 곱의 합 방식 곱셈 과정
	vector<int> num(A.size() + B.size() + 1, 0);

	for (int i = 0; i < A.size(); i++) {
		for (int j = 0; j < B.size(); j++) {
			num[i + j] += (A[i] * B[j]);
		}
	}

	//normalize(c);		// 본 문제에선 굳이 normalize 정규화 작업 필요 x
	return num;
}

/* 카라추바 알고리즘
=> 기존의 곱의 합 곱셈 처리 알고리즘에서, 그 계산 과정에서 곱셈 연산보다 덧셈/뺄셈 연산
의 수를 더 늘려 보다 더 빠른 큰 수의 곱셈을 수행하고자 하는 아이디어에서 시작함.
a x b = a1b1*10^2k + (a1b0 + a0b1)*10^k + a0b0 = z2*10*2k + z1*10^k + z0
z2 = a1 * b1;
z0 = a0 * b0;
z1 = (a0 + a1) * (b0 + b1) - z0 - z2;
*/

// a += b*(10^k)를 구현한 부분. 말 그대로 배열 간의 더하기를 표현한 것임.
void addTo(vector<int>& A, const vector<int>& B, int k) {
	A.resize(max(A.size(), B.size() + k));

	for (int i = 0; i < B.size(); i++) {
		A[i + k] += B[i];
	} // 정수의 배열 표현이므로 인덱스가 곧 10의 거듭제곱의 degree인 것

	//// 정규화 normalize. A의 각 자릿수에 대해서 Naive한 Normalize 수행
	//for (int i = 0; i < A.size(); i++) {
	//	if (A[i] > 10) {
	//		A[i + 1] += A[i] % 10;
	//		A[i] /= 10;
	//	}
	//}
}

// a -= b 를 구현한 부분. 말 그대로 배열 간의 빼기를 표현한 것임. (a >= b 가정)
void subFrom(vector<int>& A, const vector<int>& B) {
	A.resize(max(A.size(), B.size()) + 1);

	for (int i = 0; i < B.size(); i++) {
		A[i] -= B[i];
	}

	//// 정규화 normalize. 역시나 Naive하게 체크해주면 된다.
	//for (int i = 0; i < A.size(); i++) {
	//	if (A[i] < 0) {
	//		A[i] += 10;
	//		A[i + 1] -= 1;
	//	}
	//}
}

// 카라추바 알고리즘은 기본적으로 Divide & Conquer. a1 * 10^k + a0의 꼴로 분해하고 이를
// 재귀적으로 계속 나눠주는 것임. 즉, 큰 정수 두 개를 한 번에 곱하는 대신, 절반 크기로 나
// 눈 조각을 네 번 곱하는 것이다.
vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
	// a가 사이즈가 더 작으면 바꿔서 계산
	int an = a.size(), bn = b.size();
	if (an < bn) return karatsuba(b, a);

	// Base Step : a나 b가 비어있는 경우
	if (an == 0 || bn == 0) return vector<int>(); // 곱하면 빈 벡터가 반환된다.

	//system("pause");
	//Threshold : 사이즈가 50보다 작으면 그냥 Naive한 곱의 합 방식 곱셈 알고리즘 수행
	if (an <= 50) return multiply(a, b);

	int half = an / 2; // 반씩 나눈다.

	// a와 b를 반으로 나눈다.
	vector<int> a0(a.begin(), a.begin() + half);
	vector<int> a1(a.begin() + half, a.end());
	vector<int> b0(b.begin(), b.begin() + min<int>(bn, half));//<int>가 왜 붙냐
	vector<int> b1(b.begin() + min<int>(bn, half), b.end());

	// z 구하기. 이 부분이 바로 재귀적 호출이 들어가는 부분.
	vector<int> z2 = karatsuba(a1, b1);
	vector<int> z0 = karatsuba(a0, b0);

	addTo(a0, a1, 0);	// a = a1 * 10^k + a0
	addTo(b0, b1, 0);	// b = b1 * 10^k + b0

	// z1 = (a0 * b0) - z0 - z2
	vector<int> z1 = karatsuba(a0, b0);	// 역시나 이 곱셈은 재귀호출로 처리
	subFrom(z1, z0);	// 배열 표현 정수의 뺄셈 과정임.
	subFrom(z1, z2);

	// 결과를 합친다. 
	// a x b = a1b1*10^2k + (a1b0 + a0b1)*10^k + a0b0 = z2*10*2k + z1*10^k + z0
	vector<int> res;
	addTo(res, z0, 0);
	addTo(res, z1, half);
	addTo(res, z2, half * 2);

	return res;
}


void solve(const string& mems, const string& fans) {
	int n = mems.size(), m = fans.size(), cnt = 0;
	vector<int> A(n), B(m);

	for (int i = 0; i < n; i++) {
		A[i] = (mems[i] == 'M') ? 1 : 0;
	}
	for (int i = 0; i < m; i++) {
		B[m - i - 1] = (fans[i] == 'M') ? 1 : 0;
	}

	vector<int> C = karatsuba(A, B);	// 속도 향상을 위해 카라추바 알고리즘 도입

	for (int i = n - 1; i < m; i++) {
		if (C[i] == 0)
			cnt++;
	}

	cout << cnt << "\n";
}

int main() {
	int C;

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> C;
	while (C--) {
		string mems, fans;

		cin >> mems >> fans;

		solve(mems, fans);
	}
	return 0;
}