[알고스팟/C,C++] FANMEETING: 팬미팅

www.algospot.com/judge/problem/read/FANMEETING

algospot.com :: FANMEETING

되게 어려운 문제라 알고리즘 문제 해결 전략(종만북)의 풀이를 참고하여 풀었습니다.

 

예제 입력인 FFFMMM, MMMFFF의 경우를 봅시다.

 

 

이는 F는 0으로 M은 1로 바꿔, 수열의 곱으로 나타낼 수 있습니다.

 

 

팬의 경우 역순으로 곱해주면 되는데요.

 

멤버와 팬의 각 자리별 곱의 결과는 해당 팬이 해당 멤버와 포옹을 하는지 악수를 하는지를 나타냅니다.

 

가령 첫 번째 팬은 M이고, F F F M M M 의 멤버들과 포옹, 포옹, 포옹, 악수, 악수, 악수(0 0 0 1 1 1)를 하게 되죠.

 

두 번째 팬과 세 번째 팬도 마찬가지입니다.

 

네 번째 팬부터 여섯 번째 팬까지는 모든 멤버와 포옹을 합니다.

 

즉 곱셈의 결과는 첫 번째 팬이 해당 자리의 멤버와 만났을 때 총 몇 명이 악수를 하고 있는가입니다.

 

빨간 테두리 쳐진 부분을 봅시다.

 

첫 번째 팬이 마지막 멤버와 포옹을 할 때 두 번째 팬은 그 전 멤버와 포옹, 세 번째 팬은 전전 멤버와 포옹

 

모든 팬이 만나고 있는 멤버를 상대로 포옹을 함을 알 수 있습니다.

 

#include<iostream>
#include<vector>

using namespace std;

const int MAX = 200000;

void addTo(vector<int>& a, const vector<int>& b, int k) {
    int an = a.size(), bn = b.size();
    a.resize(max(an, bn + k));
    for (int i = 0; i < bn; i++) {
        a[i + k] += b[i];
    }
}

void subFrom(vector<int>& a, const vector<int>& b) {
    int an = a.size(), bn = b.size();
    a.resize(max(an, bn + 1));
    for (int i = 0; i < bn; i++) {
        a[i] -= b[i];
    }
}

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

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> b0(b.begin(), b.begin() + min(half, bn));
    vector<int> a1(a.begin() + half, a.end());
    vector<int> b1(b.begin() + min(half, bn), b.end());

    vector<int> z2 = karatsuba(a1, b1);
    vector<int> z0 = karatsuba(a0, b0);

    addTo(a0, a1, 0);
    addTo(b0, b1, 0);
    vector<int> z1 = karatsuba(a0, b0);
    subFrom(z1, z0);
    subFrom(z1, z2);

    vector<int> ret;
    addTo(ret, z0, 0);
    addTo(ret, z1, half);
    addTo(ret, z2, half * 2);

    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');
    }

    int ret = 0;

    vector<int> res = karatsuba(B, A);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << ' ';
    }
    for (int i = N - 1; i < M; i++) {
        if (res[i] == 0) ret++;
    }
    cout << endl;

    return ret;
}

int main(void)
{
    int c; cin >> c;

    for (int i = 0; i < c; i++) {
        string members, fans;
        cin >> members >> fans;
        cout << hugs(members, fans) << endl;
    }

    return 0;
}

 

하지만 일반적인 곱셈 알고리즘의 시간 복잡도는 $O(n^{2})$이기 때문에 해당 문제를 풀기엔 적절치 않습니다.

 

카라추바 알고리즘(분할정복)으로 곱셈을 구현하고

 

멤버와 팬을 각각의 수열로 나타내 곱한 결과 중,

 

모든 멤버가 팬을 만나고 있을 경우에 해당 자리의 숫자가 0이라면

 

모든 멤버와 팬이 포옹을 하고 있음을 알 수 있습니다.

 

ko.wikipedia.org/wiki/%EC%B9%B4%EB%9D%BC%EC%B6%94%EB%B0%94_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

카라추바 알고리즘 - 위키백과, 우리 모두의 백과사전