[분할 정복] FANMEETING 팬미팅

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
 
//f== 0 // m == 1 //  and
std::string fanmeeting2(const std::string& fans,const std::string& members)
{
    std::string ret(members.length() + fans.length() - 1, 'f');
 
    for (int j = 0; j < fans.size(); j++)
    {
        for(int i = 0; i < members.size(); i++)
        {
            if(members[i] == 'm' && fans[j] == 'm')
            {
                ret[i+j] = 'm';
            }
        }
    }
    return ret;
}
void subFrom(std::string &a, const std::string& b)
{
    std::cout<<"a: "<<a <<" b: "<<b<<std::endl;
    for(int i = 0; i < a.size(); i++)
    {
        if((a[i] == 'm'&& b[i] == 'm') || (a[i] == 'f' && b[i] == 'f'))
            a[i] == 'f';
        else
            a[i] == 'm';
    }
    std::cout<<"a: "<<a <<" b: "<<b<<std::endl;
}
 
// or
void addTo(std::string &a, const std::string &b, int k)
{
    int size = std::max<int>(a.size(), b.size() + k);
    for(int i = k; i < size; i++)
    {
        if(i-k >= b.size())
            break;
        if(i >= a.size())
            a += b.at(i-k);
        else if(a.at(i) == 'm' || b.at(i-k) == 'm')
        {
            a[i] = 'm';
        }
        else
            a[i] = 'f';
    }
}
int hug(std::string str, int fansize, int membersize)
{
    int count = 0;
    for(int i = membersize - 1; i < fansize; i++)
        if (str[i] == 'f')
            count++;
    return count;
}
std::string fanmeeting(const std::string& fans, const std::string& members)
{
    int mn = members.size(), fn = fans.size();
    if(fn < mn) return fanmeeting(members, fans);
 
    if(fn == 0 || mn == 0) return std::string();
 
    if(fn <= 1 || mn <= 1) return fanmeeting2(fans, members);
 
    int half = fn/2;
    int mhalf = std::min<int>(half, members.length());
//z2 = a1*b1
//z0 = a0*b0
//a0 = a0 + a1; b0 = b0 + b1
//z1 = ((a0+a1)*(b0+b1)) - z0 -z2
 
    std::string f0{fans.substr(0,half)};
    std::string f1{fans.substr(half)};
    std::string m0{members.substr(0,mhalf)};
    std::string m1{members.substr(mhalf)};
    std::string z2{fanmeeting(f1, m1)};
    std::string z0{fanmeeting(f0, m0)};
 
    addTo(f0, f1, 0); addTo(m0, m1, 0);
 
    std::string z1{fanmeeting(f0, m0)};
 
    subFrom(z1, z0);
    subFrom(z1, z2);
    std::string ret;
 
    addTo(ret, z0, 0);
    addTo(ret, z1, half);
    addTo(ret, z2, half + half);
 
    return ret;
}
 
int main(void)
{
    int testcase = 0;
    std::string fans{}, members{};
    std::cin>>testcase;
    for(int i = 0; i < testcase; i++)
    {
        std::cin>>members;
        std::cin>>fans;
//(팬 배열 에서 처음 포옹하는 멤버는 멤버 배열의 맨 마지막 멤버이므로 멤버의 배열을 뒤집어서 저장해야한다.)
        std::reverse(members.begin(), members.end());
        std::cout<<hug(fanmeeting(fans, members),fans.size(),members.size())<<std::endl;
    }
 
}
 

 

 

 팬과 멤버들을 남자끼리 포옹하지 않고

모든 멤버가 포옹을 할때의 경우의 수를 구하는 문제이다 

 

이 문제는 다음과같이 곱셈으로 표현할 수 있다.

    f*f = f         0*0 = 0

    f*m = f       0*1 = 0

    m*f = f       1*0 = 0

    m*m = m    1*1 = 1

 

 이를 통해 팬과 멤버들을 각각 곱하여 해당 자릿수에 m*m이 없는 자릿수의 개수를 세는 문제가된다는것을 알 수 있다.

 

 곱셈으로 표현한다는 점에서

이 문제는 카라츠바의 빠른 곱셈을 이용할 수 있다.

 

 이것을 구현할 떄 기존 구현인 배열이 아니라 string 객체를 사용하였는데

이 표현 때문에 함수 구현에 문제가 생겼었다.

 

    1. addTo에서 m*m이 생성되는 경우의 수를 기록해야하는데

       이를 위해 다른 변수를 생성해야함

 

    2. subFrom에서 해당 배열이 m*m이 0보다 많이 생성 될 때

       마이너스를 해서 0으로 줄여야함 1번과 마찬가지로 다른 변수에 의존해야한다.

 

 만약 데이터를 string이 아니라 array, vector 등으로 표현하여 구현했었으면

카라츠바의 빠른 곱셈에서 구현한 함수를 재사용해 문제를 풀 수 있었을 것이다.

 

     데이터의 초기 배열은 0,1로 이루어져 있으며

    두 배열을 곱하면 그 결과 배열은 0과 1이상의 숫자들로 이루어지게 된다.

    여기서 1이상의 숫자들은 m*m인 경우의 수를 뜻한다.

    karatsuba함수를 통해 각 배열을 절반으로 나누어 3개의 곱으로 나타내고

    addTo함수와 subFrom 함수를 통해 m*m인 경우의수를 병합하여 총 경우의 수를 저장한다.

    이 때 원래 구현에 쓰인 nomalize 즉 자리올림은 사용하지않는다. 

    자리 올림에 의해 m*m인 경우의 수가 생긴 자리가 변경될 수 있기 때문이다.

 

카라츠바의 빠른 곱셈을 사용한 코드의 시간 복잡도는

카라츠바 알고리즘과 마찬가지로 n^lg3이된다.

 

 

 

FANMEETING