[구현] A와 B (백준 12904)

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

12904번: A와 B

아이디어를 공부하면 좋을 거 같은 문제

 

이 문제를 푸신 다른 분들 풀이가 좋아서 공부하면 좋을 듯

https://growth-coder.tistory.com/231

[백준 12904][파이썬][그리디] A와 B

https://chocochip101.tistory.com/entry/%EB%B0%B1%EC%A4%80-12904%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC-A%EC%99%80-B

[백준] 12904번 - A와 B (파이썬) 문제 및 풀이

 

초반에 열심히 DFS 문제인 줄 알고 아래 코드처럼 풀었는데 시간 초과... DP 까지 써가면서 발악했지만 시간 초과를 넘지 못함

import copy
import sys
S = sys.stdin.readline().strip()
T = sys.stdin.readline().strip()

def do_reverse(src) :
    src = list(src)
    src.reverse()
    src = ''.join(src)

    return src

def DFS(src,tgt,memo={}) :
    if src in memo :
        return memo[src]
    
    if src == tgt :
        return True
    if len(src) > len(tgt) :
        return False

    memo[src] = DFS(src+'A',tgt) or DFS(do_reverse(src)+'B',tgt)
    return memo[src]

print(int(DFS(S+'A',T) or DFS(do_reverse(S)+'B',T)))

 

그래서 계속 고민하다 다른 풀이를 참고해보니, 결국 이건 "역으로 푸는 문제"였음

 

즉 S->T로 갈 때는 두 가지 루트가 존재하지만

 

T->S 일때는 이미 T는 주어진 결과이므로 하나의 루트만 존재하게 된다.

 

예를 들어 T가 ABBA일 때

T의 끝 값은 A이므로 S에서는 ABB에서 A를 추가했을 것이다.

 

반대로 T가 ABBB라고 하면 끝에가 B이므로

BBA에서 뒤짚어 ABB를 만든다음 B를 추가했을 것이다.

 

이렇게 역추적하면 빠른 시간 내에 S를 찾을 수 있게 되고 그것이 주어진 S와 같은 지만 체크하면 된다. 

import copy
import sys
S = sys.stdin.readline().strip()
T = sys.stdin.readline().strip()

def do_reverse(src) :
    src = list(src)
    src.reverse()
    src = ''.join(src)
    return src

flag = False
### T가 S보다 줄어들면 볼 필요도 없지.. 같을 수가 없으니
### 종료 조건에 유의하자
while len(T)>len(S) :
    if T[-1] == 'A' :
        T = T[:-1]
        if T == S :
            flag = True
            break
    if T[-1] == 'B' :
        T = T[:-1]
        T = do_reverse(T)
        if T == S :
            flag = True
            break

print(int(flag))

 

역추적으로 푸는 비슷한 문제로 백준 11501 문제도 있다니 참고하면 좋을 듯

 

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

11501번: 주식