백준 #12904 A와 B

처음 이 문제를 풀기 위해 떠올린 아이디어는 문자열에 추가할 수 있는 방법이 2가지 뿐이기 때문에 그 2가지를 현재 문자열에 모두 적용하여 dfs 처럼 내려가 답을 찾으면 멈추도록 하는 것이었다. 하지만, 이렇게 하면 당연히 답이야 나오지만 시간이 초과되는데, 너무 생각을 안하고 풀었다.

이 문제는 답을 뒤에서부터 추적해가며 풀면 정말 쉽게 풀린다. 완전 아이디어 문제인거 같다. 이 아이디어를 떠올리지 않고 풀 수 있는 방법은 사실 떠올리지 못했다.  방법만 찾으니 구현은 간단했다!

reverse 라는 함수도 이번 기회에 사용해 보게 되었는데, sort 와 사용방식이 똑같아 사용하기 쉽고 이런 문제를 풀 경우 유용할 것 같다.

 

#include <iostream>
#include <utility>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <string.h>

using namespace std;

string s,t;

string dp_func(string cur);

int main()
{
    cin>>s ;
    cin>>t;
    
    while(s.size() != t.size())
    {
        char last_one;
        last_one = t[t.size() -1];
        t.pop_back();
        if(last_one == 'B')
            reverse(t.begin(), t.end());
    }
    if(s == t)
        cout<<1;
    else
        cout<<0;
    
    return 0;
}

인생이 망해가는거 같은데 열심히 살아야한다.ㅜ