12919 - A와 B 2

info

• 문제 보기: 12919 - A와 B 2
• 소요 시간: 29분 33초
• 풀이 언어: python
• 체감 난이도: 3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

DP

풀이 코드

info

• 메모리: 31252 KB
• 시간: 36 ms

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

s = ''

def dp(t):
    global memo
    #print(t)
    if t == s:
        print(1)
        exit(0)
    
    if len(t) <= len(s):
        return
    
    # 이전 문자열 구하기
    if t[0] == 'B':
        prev = (t[1:])[::-1]
        dp(prev)
    if t[-1] == 'A':
        prev = t[:-1]
        dp(prev)
    
    return

def solution():
    global s
    s = input().rstrip()
    t = input().rstrip()
    dp(t)
    print(0)

if __name__ == '__main__':
    solution()

풀이 해설

T에서 S로 도달하기 위해 조작할 수 있는 2가지 처리 방식을 재귀로 구현한다.
단, 가능 case가 발견되는 즉시 return하지 않고 exit하는 것이 효율적이다.

메모

• S에서 T로 도달하는 것이 아닌 역방향으로 진행해야 하는 발상 때문에 3️⃣을 줌. dp 구현 난이도는 1️⃣급임