알고스팟 : 팬미팅

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

문제읽기

팬의 수는 항상 멤버의 수 이상이다. 남성 멤버와 남성 팬은 포옹하지 않는다.
여기서 모든 멤버가 동시에 포옹하는 일이 몇 번 있을지 보여라.

남성을 1로, 여성을 0으로 받아서 남성과 남성이 만나게 될 경우 $1\times1$이 되어 0 초과가 되도록 하여 0 초과일 경우 누군가는 포옹을 하지 않았음으로 놓자. 0인 경우 모두 문제 없이 포옹을 한 것이다.

예외를 설정하여 빨리 탈출하도록하자.

코드

#include<iostream>
#include<string>
using namespace std;

#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)

int hugs(const string& mem, const string& fan) {
	int N = mem.size(), M = fan.size(), hugs = 0;
	//같은 수의 사람이 있을 경우 
	if (N == M) {
		for (int i = 0; i < N; i++) {
			if (mem[i] == 'M' && fan[i] == 'M')
				return 0;
		}
		return 1;
	}
	//수가 안맞을 경우
	int cnt;
	for (int i = 0; i < (M - N + 1); i++) {
		cnt = 0;
		for (int j = 0; j < N; j++)
			if (mem[j] == 'M' && fan[i+j] == 'M')
				cnt++;
		if (cnt == 0)
			hugs++;
		
	}	
	return hugs;
}

int main() {
	int C;
	string mem, fan;
	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> mem >> fan;
		cout << hugs(mem, fan) << endl;
	}
	return 0;
}

분석

결국 시간 조건을 맞추지 못한 채로 끝을 냈다. 재귀로 가면 너무 길어질 것 같고 for문을 최대한 줄여보았지만 그럼에도 불구하고 시간초과. 다른 아이디어가 딱히 생각나지는 않아서 우선 넘어가기로 한다. 우선은 카리츠바 원리만 잘 이해한다면 될 것 같다.