FANMEETING

#include <iostream>

using namespace std;

int getHugCnt(int start, int end);
int getCenterHugCnt(int start, int end, int headPersonStart, int headPersonEnd);
bool IsAllHugged(int headPersonIdx);

const int MAX_PEOPLE_SIZE = 200001;

char inputBuffer[MAX_PEOPLE_SIZE];
char member[MAX_PEOPLE_SIZE];
char fan[MAX_PEOPLE_SIZE];

int main()
{
	int caseNum = 0;

	cin >> caseNum;
	cin.ignore();

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		cin.getline(inputBuffer, MAX_PEOPLE_SIZE);
		strncpy_s(member, inputBuffer, strlen(inputBuffer) + 1);

		cin.getline(inputBuffer, MAX_PEOPLE_SIZE);
		strncpy_s(fan, inputBuffer, strlen(inputBuffer) + 1);

		int result = getHugCnt(0, strlen(fan) - 1);

		cout << result << endl;

		memset(member, 0, sizeof(member));
		memset(fan, 0, sizeof(fan));
	}
}

int getHugCnt(int start, int end)
{
	int memberCnt = strlen(member);

	if (end - start + 1 < memberCnt) return 0;

	int mid = (start + end) / 2;
	
	int leftHugCnt = getHugCnt(start, mid);
	int rightHugCnt = getHugCnt(mid + 1, end);
	int centerHugCnt = getCenterHugCnt(start, end, mid - memberCnt + 2, mid);

	return leftHugCnt + rightHugCnt + centerHugCnt;
}

int getCenterHugCnt(int start, int end, int headPersonStart, int headPersonEnd)
{
	int hugCnt = 0;
	int memberCnt = strlen(member);

	for (int i = headPersonStart; i <= headPersonEnd; i++)
	{
		if (i < start) continue;
		if (i + memberCnt > end + 1) break;
		if (IsAllHugged(i)) hugCnt++;
	}

	return hugCnt;
}

bool IsAllHugged(int headPersonIdx)
{
	for (int i = 0; i < strlen(member); i++)
	{
		if (member[i] == 'M' && fan[headPersonIdx + i] == 'M') return false;
	}

	return true;
}

- 이번 문제도 FENCE 문제와 비슷하게 왼쪽 부분 문제, 오른쪽 부분 문제, 왼쪽과 오른쪽 모두 겹치는 부분 문제 로 나누어서 분할 정복으로 풀었다. 

- 이번에 시간을 많이 잡아 먹었던 부분은 getCenterHugCnt() 에서 for 문을 어디까지 돌려야 하는지에 관한 것이었다. 왼쪽 부분문제의 끝은 mid 값이었는데, 나는 계속해서 start ~ (mid - 1) 까지만 for 문을 돌고 있었다. 왼쪽 부분문제에 mid 가 포함되어 있는데 나는 관습적으로 왼쪽 부분 문제의 범위가 start ~ (mid - 1), 오른쪽 부분 문제의 범위가 (mid + 1) ~ end 라고 섣불리 생각하고 있었다.

FanMeetingInput.txt

FanMeetingOutput.txt