BOJ 12919 A와 B 2

https://www.acmicpc.net/problem/12919

 

백트래킹으로 풀었다.

시간을 줄이기 위한 대 똥꼬쑈

#include <bits/stdc++.h>
using namespace std;
string s, t;
bool flag = false;
map<string, int> mp;
int tACnt;
int tBCnt;
int seqA;
int seqB;
int tmpSeqA;
int tmpSeqB;

int cntA(string str)
{
    int cnt = 0;
    int tmp = 0;
    int tmp2 = 0;
    tmpSeqA = 0;
    tmpSeqB = 0;
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == 'A')
        {
            cnt++;
            tmp++;
            tmpSeqA = max(tmpSeqA, tmp);
            tmp2 = 0;
        }
        else
        {
            tmp = 0;
            tmp2++;
            tmpSeqB = max(tmpSeqB, tmp2);
        }
    }
    return cnt;
}

void go(string str)
{
    // cout << "str : " << str << "\n";
    mp[str] = 1;

    if (str.size() > t.size())
    {
        return;
    }
    if (str == t)
    {
        flag = true;
        // cout << 1 << "\n";
        // exit(0);
        return;
    }
    string r = str;
    reverse(r.begin(), r.end());
    if (t.find(str) == string::npos && t.find(r) == string::npos)
    {
    	// 여기서 가지치기가 잘되서 시간복잡도가 가장 많이 줄어든 것 같다.
        return;
    }

    int aCnt = cntA(str);
    int bCnt = str.size() - aCnt;

    if (tmpSeqA > seqA || tmpSeqB > seqB)
    {
        // cout << "seqA : " << seqA << ", tmpSeqA : " << tmpSeqA << "\n";
        return;
    }

    if (aCnt + 1 <= tACnt && !mp[str + "A"])
    {
        go(str + "A");
    }

    if (bCnt + 1 > tBCnt)
    {
        return;
    }

    string b = str + "B";
    reverse(b.begin(), b.end());
    if (!mp[b])
    {
        go(b);
    }
}

int main()
{
    cin >> s >> t;
    // go(s);
    int tmp = 0;
    int tmp2 = 0;
    for (int i = 0; i < t.size(); i++)
    {
        if (t[i] == 'A')
        {
            tACnt++;
            tmp++;
            seqA = max(seqA, tmp);
            tmp2 = 0;
        }
        else
        {
            tmp = 0;
            tmp2++;
            seqB = max(seqB, tmp2);
        }
    }

    tBCnt = t.size() - tACnt;
    // bfs(s);
    go(s);

    if (flag)
    {
        cout << 1 << "\n";
    }
    else
    {
        cout << 0 << "\n";
    }

    return 0;
}

 

문자열을 추가하는 방법이 2가지이니, 최대 시간 복잡도는  2^50이라는 말도 안되는 시간복잡도가 나오게 된다.

나는 S에서 T를 만드는 방법만 생각하고, 어떻게든 시간복잡도를 줄이기 위한 눈물의 대 똥꼬쑈를 진행했다.

문제를 풀고나서 다른분들의 풀이를 보니 S에서 T로 가는 게 아니라, T에서 S를 만들 방법으로 하신 분들이 많았다...

 

와 정말 역시 똑똑한 사람들 많구나...