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

문제출처:https://www.acmicpc.net/problem/12919

12919번: A와 B 2

1.코드

#include <iostream>
#include <algorithm>
#include <string>
 
 
using namespace std;
char arr1[51];
char arr2[51];
string s, t;
 
string del(string t) { //뒤에서 a제거
    t.pop_back();
    return t;
}
 
string rev(string t) { //뒤집고 b제거
    reverse(t.begin(), t.end());
    t.pop_back();
    return t;
}
 
bool check(string s, string t) {
    if (s.size() == t.size()) {
        if (s == t)
            return true;
        else
            return false;
    }
    if (t.size() >= 1) {
        if (t.front() == 'A' && t.back() == 'A')
            return check(s, del(t));
        if (t.front() == 'A' && t.back() == 'B')
            return false;
        if (t.front() == 'B' && t.back() == 'A')
            return check(s, del(t)) || check(s,rev(t));
        if (t.front() == 'B' && t.back() == 'B')
            return check(s, rev(t));
 
    }
    
}
 
 
 
int main() {
    scanf("%s", &arr1);
    scanf("%s", &arr2);
 
    string s = arr1;
    string t = arr2;
    
    if (check(s, t))
        printf("1");
    else
        printf("0");
}

 

2. 해결과정

s에 하나씩 추가해서 문제를 푸는 것보다 t에서 빼서  s를 만드는 것이 훨씬 편하다.

규칙을 찾아보자. 실행1은 뒤에서 A를 제거, 실행2는 뒤집고 뒤에서 B를 제거하는 경우이다.

A...A 인 경우 : 실행 1 시행

A...B 인 경우 : 연산 불가능

B...A 인 경우 : 실행 1,2 시행

B...B 인 경우 : 실행 2 시행

 

재귀적으로 함수를 호출해서 문제를 풀어주면 된다. bool 형을 이용하여 시행을 할 때마다 s와 t를 비교하고 A...B꼴이 나오면 바로 false를 출력, 나머지의 경우는 경우를 하나씩 따져가면서 t를 변형시켜 s==t가 되면 true를 리턴해주면 된다.

 

3. 느낀점

처음에는 무작정 s에 추가를 하려고 했는데 그렇게 되면 따질게 너무 많아서 힘들었다. 그래서 생각을 바꿔 t에서 제거를 하는 방향으로 풀었더니 쉽게 풀렸다!