03. 재귀 문제 [BOJ 12919번]

다나·2023년 1월 6일

재귀

코딩테스트 스터디

목록 보기

4/32

1. 관련 문제 🎯

문제 : 백준 12919 A와 B 2
난이도 : 골드 5 🔑

2. 문제 속 정보 🧩

문자열 S를 T로 바꾸는 게임이다.
이때, 문자열을 바꿀 때는 두 가지 연산만 가능하다.
1) 문자열의 뒤에 A를 추가한다.
2) 문자열의 뒤에 B를 추가하고, 문자열을 뒤집는다.

다음의 그림으로 예시를 살펴보면, S가 'A'로 주어진다고 가정하자!
1) A의 뒤에 A를 추가한다 : A -> AA
2) A의 뒤에 B를 추가하고, 문자열을 뒤집는다. A -> AB -> BA

3. 문제 속 함정 🪤

첫째 줄에 S가 둘째 줄에 T가 주어진다.
(1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

이 문제를 단순하게 생각해보면, S를 두가지 연산을 사용하여 T로 만들 수 있는지를 확인하면 된다.
따라서, S를 T의 길이가 될때까지 A를 추가하거나, B를 추가하고 문자열을 뒤집는 방식을 사용하여, S와 T가 동일한 문자열이면 1을 출력하고 동일한 문자열이 없으면 0을 출력한다.
그러나, 위의 예시에서 살펴보았듯이 A를 BABA와 살펴보기 위해서 2^3 = 8번을 살펴본다. 이처럼 2^(T의 길이-S의 길이) 만큼의 연산이 필요하다.
T의 길이는 최대 50이고, S의 길이는 최소 1이므로 최대 2^49번의 연산을 한다.
따라서, 시간 초과가 발생한다는 것을 알 수 있다.

<시간 초과된 풀이>

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

string S;
string T;
int ans = 0;

void AB(int k){
    if(k==T.length()){
        if(S == T){
            ans = 1;
        }
        return;
    }

    S += 'A';   //문자열의 뒤에 A를 추가한다.
    AB(k+1);
    S.pop_back();

    S+='B'; //문자열의 뒤에 B를 추가하고
    reverse(S.begin(), S.end());    //문자열을 뒤집는다.
    AB(k+1);
    reverse(S.begin(), S.end());
    S.pop_back();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin>>S;
    cin>>T;
    AB(S.length());
    cout<<ans<<"\n";
}

4. 문제 풀이 📒

기존의 생각을 전환해서 생각해야 한다.
S를 T로 만들 수 있는지를 살펴보는 것이 아니라, T를 S로 만들 수 있는지를 살펴본다.

따라서 문자열을 바꿀 때 사용하는 두 가지 연산을 살펴보면,
1) 문자열의 뒤에 A를 추가한다.
-> 문자열은 A로 끝난다.
2) 문자열의 뒤에 B를 추가하고, 문자열을 뒤집는다.
-> 문자열은 B로 시작한다.

예를 들어서, BABA를 살펴보자!
1) BAB 뒤에 A를 추가하여 만들어졌다. BAB -> BABA
2) ABA 뒤에 B를 추가하고, 문자열을 뒤집았다. ABA -> ABAB -> BABA

문제 풀이
1. base case : T의 길이가 S와 같을 때 (T와 S가 동일한지 비교한다.)
2. 문자열이 A로 끝나면, 맨 뒤의 A를 제거한다.
3. 문자열이 B로 시작하면, 문자열을 뒤집고 맨 뒤의 B를 제거한다.

5. 코드 🔑

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

string S;
string T;

void AB(int k){
    if(k==S.length()){
        if(S == T){
            cout<<1<<"\n";
            exit(0);	//아예 종료시킨다.
        }
        return;
    }

    if(*--T.end() == 'A'){
        T.pop_back();	// 문자열이 A로 끝나면, 맨 뒤의 A를 제거한다.
        AB(k-1);
        T.push_back('A');
    }
    if(*T.begin() == 'B'){
    	//문자열이 B로 시작하면, 문자열을 뒤집고 맨 뒤의 B를 제거한다.
        reverse(T.begin(), T.end());
        T.pop_back();
        AB(k-1);
        T.push_back('B');
        reverse(T.begin(), T.end());
    }
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin>>S;
    cin>>T;

    AB(T.length());
    cout<<0<<"\n";
}