백준 12919 A와B2 c++ // 완탐, 거꾸로탐색

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

12919번: A와 B 2

1. 거꾸로탐색

/*
    * 이진탐색 -> 2^50 -> 시간초과
    * 역발상 : target에서 start로 수렴하도록 변경!
    */

 

2. 전체코드

#include <bits/stdc++.h>
using namespace std;

string s, t,temp;
int ret;

//현재k문자열이 만들어짐
void dfs(string k) {
    //cout << k << "\n";
    //if (k.size()>t.size()) return;
    if (s == k) {
        ret = 1;
        return;
    }

    //k를 삭제하다가 빈문자열이 되는경우 -> 가망없음
    if (s.size() >= k.size()) return;
    
    if (k.back() == 'A') {
        temp = k;
        temp.pop_back();
        dfs(temp);
    }
    if (k[0] == 'B') {
        temp = k;
        temp.erase(temp.begin());
        reverse(temp.begin(), temp.end());
        dfs(temp);
    }
    return;
}
int main() {
    /*
    * 이진탐색 -> 2^50 -> 시간초과
    * 역발상 : target에서 start로 수렴하도록 변경!
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s >> t;
    dfs(t);
    cout << ret;
    return 0;
}