algospot FANMEETING

문제 링크입니다: https://algospot.com/judge/problem/read/FANMEETING

멤버와 팬의 수는 모두 1이상 200,000 이하의 정수인데 20,000으로 보고 예외처리를 해서 계속 런타임오류가 떴었습니다.

역시 문제를 끝까지 잘 읽는 것이 중요합니다...

카라츠바의 빠른 곱셈을 이용해서 풀 수 있다는 것을 몰랐다면 아마 영영 못 풀었을 것 같습니다 ㅠㅠ

/*

팬미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했다.

팬미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며

멤버들과 한명씩 포옹을 한다. 모든 팬들은 동시에 한명씩 움직인다.

남성과 남성은 포옹 대신 악수를 하고 그 외의 경우에는 포옹을 한다.

포옹하는 횟수를 계산하는 프로그램을 작성하시오

*/

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

 

//정규화 생략

/*

//num[]의 자릿수 올림을 처리한다

void normalize(vector<int> &num)

{

        num.push_back(0);

        //자릿수 올림을 처리한다

        for (int i = 0; i < num.size() - 1; i++) //num.size()-1 중요

        {

               if (num[i] < 0)

               {

                       int borrow = (abs(num[i]) + 9) / 10;

                       num[i + 1] -= borrow;

                       num[i] += borrow * 10;

               }

               else

               {

                       num[i + 1] += num[i] / 10;

                       num[i] %= 10;

               }

        }

        while (num.size() > 1 && num.back() == 0)

               num.pop_back();

}

*/

 

//두 긴 자연수의 곱을 반환한다

//각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어 있다

//예:multiply([3,2,1], [6,5,4])=123*456=56088=[8, 8, 0, 6, 5]

vector<int> multiply(const vector<int> &a, const vector<int> &b)

{

        vector<int> c(a.size() + b.size() + 1, 0);

        for (int i = 0; i < a.size(); i++)

               for (int j = 0; j < b.size(); j++)

                       c[i + j] += (a[i] * b[j]);

        //normalize(c);

        return c;

}

 

//아래 주석 처리된 addTo와 subFrom은 너무 복잡할 뿐더러 오류가 있는 코드였습니다.

//따라서 주석 밑에 간편하고 깔끔하게 다시 작성했습니다.

//아무래도 addTo 함수에 문제가 있는 것 같지만 오류가 어디서 나는지를 정확히 모르겠습니다.

//나중에 다시 한번 볼 때 발견할 수 있기를... 물론 굳이 저렇게 비효율적으로 길게 작성하지는 않을 듯 합니다.

 

/*

//a+=b*(10^k)를 구현한다

vector<int> addTo(vector<int> &a, const vector<int> &b, int k)

{

        vector<int> b1, c;

        for (int i = 0; i < k; i++)

               b1.push_back(0);

        for (int i = 0; i < b.size(); i++)

               b1.push_back(b[i]);

        c.resize(max(a.size(), b1.size() + k), 0);

        vector<int> rest = (a.size() >= b1.size()) ? a : b1; //덧셈을 마치고 더 긴 부분을 더해야한다

        int length = min(a.size(), b1.size());

 

        for (int i = 0; i<length; i++)

               c[i] += (a[i] + b1[i]);

        if (length != rest.size()) //둘의 자릿수가 다르다면

        {

               for (int i = length; i < rest.size(); i++)

                       c[i] += rest[i];

        }

        //정규화

        for (int i = 0; i < c.size(); i++)

        {

               if (c[i] > 10)

               {

                       c[i + 1] += c[i] / 10;

                       c[i] %= 10;

               }

        }

        while (c.size() > 1 && c.back() == 0)

               c.pop_back();

        return c;

}

 

//a-=b;를 구현한다 a>=b를 가정한다

vector<int> subFrom(vector<int> &a, const vector<int> &b)

{

        vector<int> c;

        c.resize(a.size());

        for (int i = 0; i < b.size(); i++)//a>=b이므로

        {

               c[i] += (a[i] - b[i]);

        }

        if (a.size() != b.size()) //둘의 자릿수가 다르다면

        {

               for (int i = b.size(); i < a.size(); i++) //나머지

                       c[i] += a[i];

        }

        //정규화

        for (int i = 0; i < c.size(); i++)

               if (c[i] < 0)

               {

                       c[i] += 10;

                       c[i + 1] -= 1;

               }

        while (c.size() > 1 && c.back() == 0)

               c.pop_back();

        return c;

}

*/

 

//a+=b*(10^k)를 구현한다

void addTo(vector<int> &a, const vector<int> &b, int k)

{

        int length = b.size();

        a.resize(max(a.size(), b.size() + k));

 

        for (int i = 0; i< length; i++)

               a[i + k] += b[i]; //이렇게 함으로써 굳이 다른 vector를 선언하지 않아도 되고 간편해졌다

        //정규화 생략

        /*

        for (int i = 0; i < a.size(); i++)

        {

               if (a[i] > 10)

               {

                       a[i + 1] += a[i] / 10;

                       a[i] %= 10;

               }

        }

        */

}

 

//a-=b;를 구현한다 a>=b를 가정한다

void subFrom(vector<int> &a, const vector<int> &b)

{

        int length = b.size();

        a.resize(max(a.size(), b.size()) + 1);

 

        for (int i = 0; i< length; i++)

               a[i] -= b[i];

        //정규화 생략

        /*

        for (int i = 0; i < a.size(); i++)

        {

               if (a[i] < 0)

               {

                       a[i] += 10;

                       a[i + 1] -= 1;

               }

        }

        */

}

 

//두 긴 정수의 곱을 반환한다

//(a0+a1)*(b0+b1)=(a0*b0)(=z0)+(a1*b0+a0*b1)(=z1)+(a1*b1)(=z2)의 원리

vector<int> karatsuba(const vector<int> &a, const vector<int> &b)

{

        int an = a.size(), bn = b.size();

        //a가 b보다 짧을 경우 둘을 바꾼다

        if (an < bn)

               return karatsuba(b, a);

        //기저 사례:a나 b가 비어있는 경우

        if (an == 0 || bn == 0)

               return vector<int>();

        //기저 사례:a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다

        if (an <= 50)

               return multiply(a, b);

        int half = an / 2;

        //a와 b를 밑에서 half자리와 나머지로 분리한다

        vector<int> a0(a.begin(), a.begin() + half);

        vector<int> a1(a.begin() + half, a.end());

        vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));

        vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());

        //z2=a1*b1

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

        //z0=a0*b0

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

        //a0=a0+a1;

        //b0=b0+b1

        addTo(a0, a1, 0);

        addTo(b0, b1, 0);

        //z1=(a0+a1)*(b0+b1)-z0-z2

        vector<int> z1 = karatsuba(a0, b0);

        subFrom(z1, z0);

        subFrom(z1, z2);

        //result=z0+z1*10^half+z2*10^(half*2)

        vector<int> result;

        addTo(result, z0, 0);

        addTo(result, z1, half);

        addTo(result, z2, half + half);

        return result;

}

 

/*

카라츠바의 빠른 곱셈을 이용해 팬미팅 문제를 해결하는 함수

*/

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') ? 1 : 0;

        for (int i = 0; i < M; i++)

               B[M - i - 1] = (fans[i] == 'M') ? 1 : 0;

        //karatsuba 알고리즘에서 자리 올림은 생략한다

        vector<int> C = karatsuba(A, B); //남자와 남자가 껴안을 경우 1, 그 외 0

        int allHugs = 0;

        for (int i = N - 1; i < M; i++)

               if (C[i] == 0)

                       allHugs++;

        return allHugs;

}

 

int main(void)

{

        int test_case;

        string members, fans;

 

        cin >> test_case;

        if (test_case < 0 || test_case>20)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               cin >> members >> fans;

               if (members.size() < 1 || fans.size() < 1 || members.size() > 200000 || fans.size() > 200000)

                       exit(-1);

               cout << hugs(members, fans) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]