[백준][C++] 12919번: A와 B 2 <180>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

생각의 흐름

이 문제는 문자 S => T를 직접 만들려하면 해결할수가 없는 문제이다.

매번 2가지 선택 사항이 있는데, 문자열의 총 길이가 49까지 가능하니, 2^49가 되므로, 시간초과가 발생할것이다.

 

따라서 역으로 T => S로 조건에 맞게 변경이 가능한지를 확인해야 한다.

 

조건 1) 주어진 S의 문자열 맨 끝이 'A'라면 맨 뒤 문자 하나를 제거해 준다.

조건 2) 주어진 문자열 S의 맨앞 문자가 'B'라면, 문자열 전체를 뒤집은 후 맨뒤로온 'B'를 제거해 준다.

 

여기서 주의할점이 1번과 2번 조건을 else if 로 묶으면 안된다. 즉 다음과 같이 되면 안된다.

if(t[t.size()-1] == 'A'){
  ...
}else if(t[0] == 'B'){
  ...
}

else if 로 묶여 버리면, 문자열은 항상 뒤가 'A' 이거나, 맨앞이 'B'이거나 둘중 하나이여만 한다.

 

하지만 다음과 같은 반례가 있다.

'BBABAABA' 이 문자열은 맨 앞이 'B' 이고, 맨 뒤는 'A'이다 따라서 조건 1, 2중 어떤 것에서 변경된것인지 알수가 없다.

'BBABAAB' 에서 조건 1에 의해 맨 뒤에 'A'가 추가된것 일수도 있고

'ABAABAB' 에서 조건 2에 의해 맨 뒤에 'B'가 추가되고 뒤집힌것 일수도 있다.

 

따라서 if 문 2개로 변경해주어야 한다.

if(t[t.size()-1] == 'A'){
  ...
}
if(t[0] == 'B'){
  ...
}

두 조건중 만족하는 조건은 모두 확인을 해봐야 하기 때문이다.

 

나의 코드

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

void go(string s, string t){
    if(s == t){
        cout << 1;
        exit(0);
    }
    if(s.length() > t.length()){
        return;
    }

    if(t[t.size()-1] == 'A'){
        string temp = t;
        temp.erase(temp.size()-1);
        go(s, temp);
    }

    if(t[0] == 'B'){
        string temp = t;
        reverse(temp.begin(), temp.end());
        temp.erase(temp.size()-1);
        go(s, temp);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string S, T;
    cin >> S >> T;

    go(S, T);
    cout << 0;

    return 0;
}