[백준 12919] - A와 B 2(완전탐색) C++

문제

https://www.acmicpc.net/problem/12919

12919번: A와 B 2

접근방법

S에서부터 시작하는 방법은 2^50의 시간이 걸려서 불가능하다.

 

거꾸로 T에서 시작해 하나씩 지워나간다면, 경우의 수를 줄일 수 있다.

 

T에서 시작하는 경우,

1. 맨 뒤의 문자가 'A'인 경우 -> 삭제

2. 맨 앞의 문자가 'B'인 경우 -> 삭제

3. 맨 뒤의 문자가 'B'인 경우 -> 삭제 불가

4. 맨 앞의 문자가 'A'인 경우 -> 사제 불가

 

보다시피 삭제할 수 있는 경우가 한정적이기 때문에, 시간을 절약할 수 있다.

 

아래 코드보다 더 효율적으로 하는 방법은 투포인터를 활용하면 된다. 나는 차마 그 생각까지는 하지 못했다.

코드

string S, T;
map<string, bool> cache;         //한번 방문했지만, 정답이 아닌 것은 -1임.
void solution(string cand) {
    if (cand.size() < S.size()) return;
    cache[cand] = true;
    if (cand[cand.size() - 1] == 'A') solution(cand.substr(0, cand.size()-1));
    if (cand[0] == 'B') {
        reverse(cand.begin(), cand.end());
        solution(cand.substr(0, cand.size() - 1));
    }
    
}

int main() {
    cin >> S >> T;
    solution(T);
    cout << cache[S] << endl;
}

개선할 점

T에서부터 거꾸로 탐색해도 어차피 2^50의 경우의 수를 가질 거라고 생각해서

다른 방법을 한참 찾았다.

 

거꾸로 한다면 가지를 자를 수 있는 방법이 있을 거라는 생각을 못했던 게 아쉽다.