[골드 5] A와 B 2

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

12919번: A와 B 2

3가지 풀이 방법

1. T를 S로 만들기 문자열이 뒤집어졌는지 boolean으로 표현하기

2. T를 S로 만들기 문자열을 실제로 뒤집기

3. S로 T를 만들기

 

T를 S로 만들 때는 맨 앞에 B가 있거나 맨뒤에 A가 있으면 재귀를 타고 들어가서 값이 씻음

근데 S를 T로 만들 때는

S가 1이고 T가 50이면 중복 잘 모르겠고 일단 최악은 2^49 임

 

그러면 S는 어떻게 값이 싸게 갈 것이냐 고민했을 때

T의 모든 substring + substring의 reverse를 구해서 그것 조차 아니라면 그거는 더 이상 해볼 필요도 없는 거지

그러고 TCandidates에서도 방문 표시를 해서 시간을 절감시키자