7.6문제: 팬미팅(ID:FANMEETING)

문제

가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 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

First Thoughts

fan과 member의 대응

내가 생각한 접근 방법은 fan과 member의 성별을 한명 한명 비교해보는 것이다. 앞 문제에서 string으로 입력받아 iterator을 사용한 것이 인상깊었는지 iterator을 사용하여 재귀호출을 하도록 구현하였다. 베이스 케이스로는 member의 수와 비교해야되는 팬의 수를 비교하여 팬의 수가 적으면 0을 반환하도록 하였다. 또한 fan과 member의 마지막 사람의 성별이 둘 다 M일 때 역시 0을 반환한다. 그리고 순회과정에서 한 쌍이라도 M으로 이루어져있다면 fan의 처음 사람을 다음 사람으로 옮긴다.

My Code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
string member;
string fan;
int check(string::iterator& ms, string::iterator& fs) {
	string::iterator i, j;
	int size = fan.end() - fs;
	if (size<member.size())
		return 0;
	for (i = ms, j = fs; i != member.end(); i++, j++) {
		
		if (j == fan.end()&&i!=member.end())
			return 0;
		else if (j == fan.end() && i == member.end()) {
			if (*j == 'M' && *i == 'M')
				return 0;
			else
				return 1;
		}
		
		if (*i == 'M' && *j == 'M') {
			return check(ms, ++fs);
		}
	}
	return 1+check(ms,++fs);
}

int main(void) {
	int C;
	int N, M;
	int i;
	
	cin >> C;
	for (i = 0; i < C; i++) {
		cin >> member;
		cin >> fan;
		string::iterator ms = member.begin();
		string::iterator fs = fan.begin();
		cout << check(ms, fs)<<endl;
	}
}

Answer Code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
string member;
string fan;

vector<int> multiply(const vector<int>& a, const vector<int>& b) {
	vector<int> c(a.size() + b.size() + 1, 0);
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < b.size(); j++) {
			c[i + j] += a[i] * b[j];
		}
	}
	return c;
}

//카라츠바의 빠른 정수 곱셈 알고리즘
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];
	}
}
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];
	}
}
vector<int> karatsuba(const vector<int>& a, const vector <int>& b) {
	int an = a.size(), bn = b.size();
	if (an < bn)
		return karatsuba(b, a);
	if (an == 0 || bn == 0)
		return vector<int>();
	if (an <= 50)
		return multiply(a, b);
	int half = an / 2;
	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>(b.size(), half));
	vector<int>b1(b.begin() + min<int>(b.size(), half), b.end());

	//z2=a1*b1
	vector<int> z2 = karatsuba(a1, b1);
	//z0=z0*b0
	vector<int> z0 = karatsuba(a0, b0);
	//a0=a0+a1
	addTo(a0, a1, 0);
	//b0=b0+b1
	addTo(b0, b1, 0);

	//z1=(a0*b0)-z0-z2
	vector<int>z1 = karatsuba(a0, b0);
	subFrom(z1, z0);
	subFrom(z1, z2);

	//ret=z0+z1*10^half+z2*10^(half*2)
	vector<int> ret;
	addTo(ret, z0, 0);
	addTo(ret, z1, half);
	addTo(ret, z2, half + half);
	return ret;
}

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 allHugs = 0;
	for (int i = N - 1; i < M; i++) {//N-1번째부터 모든 멤버가 팬과 짝을 이룸
		if (C[i] == 0)
			++allHugs;
	}
	return allHugs;
}

int main(void) {
	int C;
	int N, M;
	int i;
	
	cin >> C;
	for (i = 0; i < C; i++) {
		cin >> member;
		cin >> fan;
		string::iterator ms = member.begin();
		string::iterator fs = fan.begin();
		cout << hugs(member,fan)<<endl;
	}

}

Difference & Faults

시간 초과

내가 작성한 코드는 이중for문의 사용으로 O($n^2$)임은 분명하다. 그래서 시간 초과 또한 예상은 했다. 하지만 이 문제를 분할을 사용하여 어떻게 풀이해야할지 도통 생각이 나지 않았다.

곱셈의 사용

책의 정답 코드는 앞에 예제로 나온 카르츠바의 곱셈을 사용하였다. 두 수를 곱셈으로 풀이하기 위해 두 성별을 숫자로 표현했다는 점과 'M'과 'M'의 예외적인 관계를 1과 1의 관계로 했다는 점이 매우 다르다.

Impressions

경험에서 나오는 창의력

앞서 말했듯이 책의 해답 코드를 보면 '카르츠바의 곱셈'을 무조건적으로 알아야한다. '카르츠바의 곱셈'이라는 것을 알지는 못해도 최소한 두 식을 곱하는 방법을 알아야한다. 그런데 그런 문제를 풀어본 경험이 있어도 이 문제를 보며 그 경험을 떠올리긴 힘들었을 것이다. 그래서 이 문제를 보며 느낀 것은 좀 특이한 방식의 풀이는 메모를 해두고 두고두고 익혀둘 필요가 있어보인다.

Summary

이번 문제는 너무 발상적이었다. 이걸 보고 카르츠바의 곱셈으로 풀이한다는 것은 그냥 분할 정복을 사용하기 위해 사용한 풀이 같다. 다른 사람들은 이 문제를 보고 어떤 식으로 풀었을지 또 책의 풀이를 보고 어떤 생각을 했을지 궁금하다. 나중에 이런 류의 문제를 보고 그 때 '카르츠바의 곱셈'을 사용할 수 있을 지도 의문이다.