🔍 12904 A와 B

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

---

🤔 풀이

• 가장 먼저 생각난 풀이 : S에서 조건1 또는 조건2를 선택하며 dfs방식으로 푼다. → $O(2^{1000}=10^{3*100}=10^{8*40})$ 즉, 최악의 경우 약 40초가 걸린다 시간 초과로 실패하는 풀이.

• 사실 T의 뒷문자로 조건이 한 가지로 한정되는 문제이다.
  ex)
  - 문자열의 뒤에 A를 추가한다. → T의 뒷문자는 A가 된다.
  - 문자열을 뒤집고 뒤에 B를 추가한다. → T의 뒷문자는 B가 된다.
  

• 따라서 T의 뒷문자를 보고 조건을 판단 뒤 해당 조건을 적용하기 전으로 되돌리는 것을 반복하여, S와 같은 길이가 되었을 때 만들어진 T가 동일한지 확인하면 된다.
  

---

📝 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string S, T;
int ans = 0;

int main() {
    cin >> S >> T;

    int s_leng = S.length();
    int t_leng = T.length();
    for (int j = 0; j < t_leng-s_leng; j++) {
        if (T[T.length()-1] == 'B') { // 뒤집고 B를 추가한 경우.
            T.erase(--T.end());
            reverse(T.begin(), T.end());
        }
        else { // A를 추가한 경우.
            T.erase(--T.end());
        }
    }

    if (T.compare(S) == 0) {
        ans = 1;
    }


    cout << ans;
    return 0;
}

🔍 12919 A와 B 2

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

---

🤔 풀이

• 가장 먼저 생각 난 풀이 : 문자열 길이가 줄어들었지만, 이 또한 12904번 A와 B 문제처럼 dfs로 풀시 시간초과가 난다. $O(2^{50}=10^{15})$ 즉 약 2초 초과

• 해당 문제도 조건을 살펴보자.
  ex)
  - 문자열의 뒤에 A를 추가한다. → T의 뒷문자는 A가 된다. (앞문자는 A, B 모두 될 수 있다.)
  - 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. → T의 앞문자는 B가 된다. (뒷문자는 A, B 모두 될 수 있다.)
  

• 따라서 T의 앞문자와, 뒷문자를 보고 조건을 판단 뒤 해당 조건을 적용하기 전으로 되돌리는것을 반복하여, S와 같은 길이가 되었을 때 만들어진 T가 동일한지 확인하면 된다. (둘 다 해당될수있으므로 두 조건을 if-else문으로 묶는일은 없도록 해야한다.)

---

📝 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string S, T;
int ans = 0;

void dfs(string s) {
    if (s.length() <= S.length()) {
        if (S.compare(s) == 0) ans = 1;
        return ;
    }
    
    if (s[s.length()-1] == 'A') { // 1. A를 추가 -> A가 뒷자리
        string s_temp = s;
        s_temp.erase(s_temp.end()-1);
        dfs(s_temp);
    }

    if (s[0] == 'B') { // 2. B를 추가하고 뒤집 -> B가 앞자리
        string s_temp = s;
        s_temp.erase(s_temp.begin());
        reverse(s_temp.begin(), s_temp.end());
        dfs(s_temp);
    }
}

int main() {
    cin >> S >> T;
    dfs(T);
    cout << ans;
    return 0;
}