[알고스팟] 팬 미팅

문제 링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • FANMEETING
  • 15000ms
  • 65536kb
  • 4020
  • 560 (13%)
• • 출제자
  • 출처
  • 분류
• • Yongrok
  • RUN Programming Contest, Fall 2009
  • 보기

문제

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

어떻게 접근할까?

 위 문제는 '곱셈 연산'으로 접근이 가능합니다. 아래 그림을 통해 알아보겠습니다.

 

곱셈을 하면 위와 같이 결과가 나오게 됩니다.

현재 포옹을 하지 않는 조건은, 

1. 남자 팬과 남자 가수가 만나서 악수를 하는 경우

2. 가수와 팬이 만나지 않아서 악수를 하지 않는 경우 

두 가지 입니다.

따라서, 악수를 하는 경우는 남자 팬과 남자 가수가 만나는 경우이므로, M이면 1이라고 생각하고, F인 경우는 0 으로 설정합니다.

이렇게 하면 악수를 하는 경우는 1과 1이 곱해져 1의 결과를 가지게 되고, 나머지의 경우는 악수를 하지 않는 0의 결과를 가집니다.

따라서 아주 큰 수의 곱셈을 시행하고, 

가수가 모두 들어오기 시작하는 가수의 수 - 1 자리수 부터 팬의 수 까지 0의 개수를 확인하면 그것이 바로 답이 됩니다.

그리고 주의해야 할 것이 있습니다. 바로 곱하기를 한 경우를 보면, 가수의 맨 앞의 사람이 팬의 맨 앞의 사람부터 만나는 것을 볼 수 있습니다.

문제의 그림에 따르면 가수 맨 앞의 사람은 팬의 맨 뒤의 사람부터 만나서 악수를 시작합니다.

따라서, 팬의 수를 거꾸로 뒤집고 곱하기를 해야한다는 것 입니다.

이제 곱하기를 구현하면 되는데, 보통의 곱하기는 O(n^2)의 시간복잡도를 가집니다.

아주 큰 수의 곱하기를 O(n^log 3)의 시간 복잡도를 가지도록 풀 수 있게 해주는 알고리즘이 있습니다.

이름은 '카라츠바 알고리즘' 입니다.

분할 정복을 통해서 곱셈을 자리수에 따라서 반씩 나누어서 더하면서 진행하는 방식입니다.

카리츠바 알고리즘은 다른 곳에 포스팅을 했으니 필요하면 보도록 합시다!

카리츠바 알고리즘 알아가기!

이렇게 카라츠바 알고리즘을 통해서 곱셈의 결과를 얻게 된다면, 위에서 말했던 자리수 범위에서 0이 몇 개인지 출력하면 됩니다!

왜냐하면, 1이 된다는 것은 악수를 하는 사람이 있다는 것을 의미하기 때문입니다! (M이 1이고 M과 M이 곱해져야만 1이 나옵니다.)

코드

#pragma once
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
 
using namespace std;
 
char groups[200001];
char fans[200001];
 
int len[2];
 
typedef vector<int> VEC;
 
vector<int> g, f;
 
int min(int i1, int i2)
{
    return i1 < i2 ? i1 : i2;
}
 
int max(int i1, int i2)
{
    return i1 > i2 ? i1 : i2;
}
 
VEC multi(VEC& A, VEC& B)
{
    int s1 = A.size();
    int s2 = B.size();
 
    VEC res;  
    res.resize(s1 + s2 - 1, 0);
 
    for (int i = 0; i < s1; i++)
    {
        for (int j = 0; j < s2; j++)
        {
            res[i + j] += A[i] * B[j];
        }
    }
    return res;
}
 
void add(vector<int>& vec1, vector<int>& vec2, int k)
{    
    int s = max(vec2.size() + k, vec1.size());
 
    vec1.resize(s, 0);
    vec2.resize(s, 0);
 
    for (int i = 0; i < s - k; i++)
    {
        vec1[i + k] += vec2[i];
    }
    
}
 
void sub(vector<int>& vec1, vector<int>& vec2)
{
    int s = max(vec1.size(),vec2.size());
 
    vec1.resize(s, 0);
    vec2.resize(s, 0);
 
    for (int i = 0; i < s; i++) vec1[i] -= vec2[i];
}
 
VEC Karatsuba(VEC& A, VEC& B)
{
    if (A.size() < 50)
    {
        VEC res;
        res = multi(A,B);
        return res;
    }
 
    int half = A.size() / 2;
    
    if (A.empty() || B.empty()) return VEC();
 
    VEC a1 = VEC(A.begin(), A.begin() + half);
    VEC a0 = VEC(A.begin() + half, A.end());
    VEC b1 = VEC(B.begin(), B.begin() + min(half, B.size()));
    VEC b0 = VEC(B.begin() + min(half, B.size()), B.end());
 
    VEC z0, z1, z2;
    
    z0 = Karatsuba(a0, b0);
    z2 = Karatsuba(a1, b1);
    
    add(a0, a1, 0);
    add(b0, b1, 0);
 
    z1 = Karatsuba(a0, b0);
    sub(z1, z0);
    sub(z1, z2);
 
    VEC res;
    add(res, z2, 0);
    add(res, z1, half);
    add(res, z0, half + half);
 
    return res;
}
 
int FANMEETING()
{
    int t;
    scanf("%d\n", &t);
 
    while (t--)
    {
        scanf("%s\n", groups);
        scanf("%s\n", fans);
 
        len[0] = strlen(groups);
        len[1] = strlen(fans);
 
        f.resize(len[1], 0);
        g.resize(len[0], 0);
        for (int i = 0; i < len[0]; i++) g[i] = groups[len[0] - i - 1] == 'M';
        for (int i = 0; i < len[1]; i++) f[i] = fans[i] == 'M';
 
        VEC res = Karatsuba(f, g);
 
        int cnt = 0;
        for (int i = len[0] - 1; i < len[1]; i++)
        {
            cnt += res[i] == 0;
        }
        printf("%d\n", cnt);
    }
 
    return 0;
}