백준 9252 파이썬 python 재귀 풀이

백준 9252번을 탑다운 방식(재귀) 로 풀어봤습니다. 

 

findAnswer 함수에서 

return 문의 위치를 처음에 if 문 안에 잘못 써서 디버깅에 어려움을 겪었습니다.. (vscode 복사 붙여넣기 과정에서 잘못됨)

 

AI 에게 물어봐도 바텀업 방식(반복문) 만 알려주고 블로그에도 재귀 풀이는 보이지 않아, 재귀 풀이를 업로드 합니다! 

import sys 

input = sys.stdin.readline 

sys.setrecursionlimit(10**6)

first = input().strip()
second = input().strip() 

dp = [[] for i in range(len(first))]

for i in range(len(first)):
    for j in range(len(second)):
        dp[i].append(-1)


ans = []

def solve(i, j):

    if i == 0:
        dp[i][j] = 0
        if first[i] in second[:j+1]:
            dp[i][j] = 1 
            
        return dp[i][j]
    
    if j == 0:
        dp[i][j] = 0
        if second[j] in first[:i+1]:
            dp[i][j] = 1 
            
        return dp[i][j]
    
    if dp[i][j] != -1:
        return dp[i][j]
    
    if first[i] == second[j]:
        dp[i][j] = solve(i-1,j-1) + 1
    else:
        dp[i][j] = max(solve(i-1,j), solve(i,j-1))

    return dp[i][j]


length = solve(len(first) - 1, len(second) - 1)
print(length)
    
ans = []

def findAnswer(i, j):

    if i == 0:
        if first[i] in second[:j+1]:
            ans.append(first[i])
        return
    if j == 0:
        if second[j] in first[:i+1]:
            ans.append(second[j])
        return

    if first[i] == second[j]:
        ans.append(first[i])
        findAnswer(i-1,j-1)
    else:
        if dp[i-1][j] > dp[i][j-1]:
            findAnswer(i-1, j)
        else:
            findAnswer(i, j-1)
        
if length > 0:
    findAnswer(len(first) - 1, len(second) - 1)
    print("".join(reversed(ans)))