백준 12919번 A와 B 2 (C++)

문제 링크 : https://www.acmicpc.net/problem/12919

12919번: A와 B 2

문제 요약

 

1. 문자열 S와 T가 주어집니다.  (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

2. 문자열 S를 변형시킬 수 있는 방법은 2가지 입니다.

(1) 문자열 뒤에 A를 추가

(2) 문자열 뒤에 B를 추가하고 뒤집기

3. 주어진 조건을 이용하여 S를 T로 변경시킬 수 있으면 1을 출력, 그렇지 않으면 0을 출력하세요.

 

핵심 포인트

 

문자열 S에 'A'와 'B'를 하나씩 추가하여 T를 만들어내도록 확인하는 것은 불가능합니다.

연산의 최대 가짓수가 2^50이 되므로, 시간초과가 발생하기 때문입니다.

때문에 T에서 조건에 맞게 문자를 제거하여 S로 만드는 방식을 선택해야 합니다.

 

문제 풀이

 

코드 자체가 간결한 편이므로, 전체코드에서 핵심만 설명하도록 하겠습니다.

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

string temp = "";

void abGame(string s, string t){
    if(s==t){ // 3 
        cout << 1 << "\n";
        exit(0);
    }
    if(s.size()>=t.size()) return; // 4
    if(t[t.size()-1]=='A'){ // 1
        temp = t;
        temp.erase(temp.size()-1);
        abGame(s,temp);
    }
    if(t[0]=='B'){ // 2
        temp = t;
        temp.erase(temp.begin());
        reverse(temp.begin(),temp.end());
        abGame(s,temp);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string s,t;
    cin >> s >> t;
    abGame(s,t);
    cout << 0 << "\n";
    return 0;
}

(1) 만약 T문자열의 맨 끝이 'A'라면, temp에 문자열 T를 저장한 뒤 temp에서 맨뒤 'A'를 제거합니다.

그리고 다시 재귀함수를 통해 S와 temp를 비교합니다.

(2) 만약 T문자열의 맨 앞이 'B'라면, temp에 문자열 T를 저장한 뒤 temp에서 맨앞 'B'를 제거합니다.

그런다음 temp를 뒤집습니다. 이렇게하면 B를 추가하기 이전의 원본 문자열이 나옵니다.

그리고 다시 재귀함수를 통해 S와 temp를 비교합니다.

(3) S와 T가 같다면 1을 출력하고 종료합니다.

(4) 만약 S의 사이즈 >=  T의 사이즈라면 return 합니다.