[BOJ|PYTHON]백준20047 - DP TOPDOWN

세상에서 제일 화나는 TOP DOWN DP 유형이다.

저번 글에서 본 것처럼 DP-TOPDOWN의 형식적인 코드는 다음과 같다 (느낌만 알아두자)

def topdown:
     if 마지막 노드에 다다른 조건:
           return ~~
     if 이미 DP 테이블에 값이 있다면(memoization):
           return 그냥 그거 가져온다.
     #밑에 있는 노드를 호출해서 답 갱신 + 필요하다면 DP 테이블에도 값 갱신
     DP[][]+= 또는 min .. topdown() 
     return 해당 노드값

 

이 문제에서는 ‘되냐 안되냐’의 문제를 다룬다. 이럴 때 0, 1, max를 사용해서 풀 수 있다. 만약 조건에 만족하는 것이 하나라도 나올 시에는 return 1을 하고 안 나오면 계속 return 0을 한다.

memoization 방법은 딱히 없지만 이 return 값들을 이용해서 계속 앞에서 뒤의 값들을 가지고 오는데 max값으로 가져오게 되어 항상 return 0이라면 그냥 0만 주구장창 가져오게 되지만

한 번이라도 return 1이라면 max(1,0) =1 로 있는 경우가 하나라도 생기게 되어 최종 return 값은 1이 되어 dfs(0,0,0)이 직접적으로 최종return하게 되는 것은 1 또는 0이다.

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

N=int(input())
before=input()
after=input()

one,two=map(int,input().split())
newbefore=''
for i in range(N):
    if i==one or i==two:continue
    newbefore+=before[i]

#인자: 현재 어디, 몇개가 맞니, cnt(몇 개 썼는가), 
def dfs(index,correct,cnt):
    #print(index,correct,cnt)
    if correct==N:
        if cnt==2: return 1
        else: return 0

    ret=0

    if index<N-2 and newbefore[index]==after[correct]: ret=max(ret,dfs(index+1,correct+1,cnt))
    if cnt==0 and after[correct]==before[one]: ret=max(ret,dfs(index,correct+1,cnt+1))
    if cnt==1 and after[correct]==before[two]: ret=max(ret,dfs(index,correct+1,cnt+1))

    return ret
if dfs(0,0,0): print("YES")
else: print("NO")

'''
3
oxo
xoo
1 2

4
oxoo
xooo
1 2

4
oxox
xoxo
1 3

4
xxxo
oxxx
1 3
NO
'''