[#2-5]분할정복-문제: 팬미팅(문제 ID: FANMEETING)

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135

#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; 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(); } 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; } void addTo(vector<int>& a, const vector<int>& b, int k) {     if (a.size() < b.size() + k)         a.resize(b.size() + k);     a.push_back(0); //덧셈시 자릿수 증가를 위해 미리 공간 확보를 위한 삽입     for (int i = a.size(); i < a.size(); i++)         a[i] = 0;     for (int i = 0; i < b.size(); i++)         a[i + k] += b[i];     //normalize(a); } void subFrom(vector<int> &a, vector<int> &b) {     for (int i = 0; i < b.size(); i++)         a[i] -= b[i]; } 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가 비교적 짧은 경우 0(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 알고리즘에서 자리 올림은 생략한다. 어차피 0,1로만 곱셈을 사용할 거라 올림이 필요없다     vector<int> C = karatsuba(A, B);     int allHugs = 0;     for (int i = N - 1; i < M; i++)     if (C[i] == 0)         ++allHugs; //남자와 남자가 만난 경우 즉 1*1 = 1인 경우만 체크안하면 되므로 0일 경우 카운트 증가     return allHugs; } int main(int argc, char *argv[]) {     int Testcase;     string members, fans;     cin >> Testcase;     if (Testcase <= 0 && Testcase > 50)         return 0;     for (int i = 0; i < Testcase; i++)     {         cin >> members;         cin >> fans;         if (1 >= members.size() || members.size()>200000 || 1 >= fans.size() || fans.size() > 200000)             return 0;         cout << hugs(members, fans) << endl;     }     return 0; } Colored by Color Scripter

cs