No Limitation
[구현] A와 B (백준 12904) 본문
https://www.acmicpc.net/problem/12904
아이디어를 공부하면 좋을 거 같은 문제
이 문제를 푸신 다른 분들 풀이가 좋아서 공부하면 좋을 듯
https://growth-coder.tistory.com/231
초반에 열심히 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
'프로그래밍' 카테고리의 다른 글
[완전탐색-Union Find] 전력망 둘로 나누기 (0) | 2024.04.02 |
---|---|
[구현] 삼각달팽이 - 공부용 (0) | 2024.04.01 |
[완전탐색-DFS] 피로도 (0) | 2024.03.31 |
[최대 힙 기초] 이중우선순위큐 (1) | 2024.03.30 |
[BFS] 트리의 부모 노드 찾기 (0) | 2024.03.28 |