Axolotl

BOJ 12919 A와 B 2

16 Dec 2024
PS Algorithm

BOJ 12904 A와 B 문제와는 다르게 B를 추가하는 연산이 다릅니다. 문자열 뒤에 B를 추가하고 문자열을 뒤집기 때문에 12904 문제와는 달리 경우의 수가 나뉠 수 있습니다. 이번 문제에서는 문자열 S와 T의 길이가 50 이하인 것에서 아이디어를 착안하면 연산을 재귀적으로 S와 T의 길이가 같아질 때까지 브루트포스하게 탐색할 수 있습니다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <string.h>
#include <algorithm> 

using namespace std; 

string S, T; 
int lenT, lenS = S.length(); 
int flag = 0; 

void solve(string str){
    lenT = str.length(); 
    if(str == S){
        flag = 1; 
        return; 
    }
    if(lenT <= lenS){
        return; 
    }
    if(str[lenT - 1] == 'B' && str[0] == 'A'){
        return; 
    }
    
    if(str[lenT - 1] == 'A') {
        string tmp = str; 
        tmp.pop_back(); 
        solve(tmp); 
    }
    if(str[0] == 'B') {
        string tmp = str; 
        reverse(tmp.begin(), tmp.end());
        tmp.pop_back();
        solve(tmp); 
    }
}

int main() {
    cin >> S >> T; 
    solve(T); 
    cout << flag; 
}