8913. 문자열 뽑기

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

Solution

Keyword

처음에 dp로 접근했다가 중간에서 삭제 될 경우 처리가 어려워져서 완전탐색을 생각했으나 케이스가 너무 많았다.
여기서 나올 수 있는 문자열의 최대 경우의 수가 2^25이고 제거되는 길이가 2 이상임을 감안하여 map으로 문자열을 저장하면서 1번만 방문하게 하도록 처리했더니 통과할 수 있었다.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int t;
string s;
map<string, int> mp;

int solve(string &cur)
{
    if (cur.size() == 0) return 1;
    if (mp.count(cur)) return mp[cur];
    mp[cur] = 0;
    int st = 0, ed = 0;
    for (int i = 0; i < (int)cur.size() - 1; i++)
    {
        if (cur[i] == cur[i + 1])
            ed = i + 1;
        else
        {
            if (ed - st + 1 >= 2)
            {
                string tmp = cur.substr(0, st);
                if (ed + 1 < cur.size()) tmp += cur.substr(ed + 1);
                mp[cur] |= solve(tmp);
            }
            st = ed = i + 1;
        }
    }

    if (ed - st + 1 >= 2)
    {
        string tmp = cur.substr(0, st);
        if (ed + 1 < cur.size()) tmp += cur.substr(ed + 1);
        mp[cur] |= solve(tmp);
    }

    return mp[cur];
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--)
    {
        mp.clear(); cin >> s;
        cout << solve(s) << "\n";
    }
}