백준 9251 [LCS] 파이썬

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

9251번: LCS

알고리즘 시간에 직접 구현해 보지는 않았지만, 간단히 이론적으로 배운적이 있었다. 그때의 기억이 떠오르면서, 비교하는 것 까지는 생각이 났지만, 구체적으로 어떻게 비교를 해야할지 모르겠었다...

#백준 9251 LCS
import sys
input=sys.stdin.readline
f=list(map(str,input().rstrip()))
s=list(map(str,input().rstrip()))
f_len=len(f)
s_len=len(s)
dp=[[0]*(s_len) for _ in range(f_len)]
for j in range(s_len):
    if f[0]==s[j]:
        dp[0][j]=1
for i in range(f_len):
    if f[i]==s[0]:
        dp[i][0]=1
for i in range(1,f_len):
    for j in range(1,s_len):
        M=0
        for k in range(i):
            M=max(dp[k][j-1],M)
        dp[i][j]=max(max(dp[i-1][:j]),M)
        if f[i]==s[j]:
            dp[i][j]+=1

for i in range(f_len):
    M=max(M,max(dp[i]))

print(M)

시간 초과가 발생하였다.

 

고민을 하다 다른분의 코드를 참고하여 문제를 해결하였다.

 

#백준 9251 LCS
import sys
input=sys.stdin.readline
f=list(map(str,input().rstrip()))
s=list(map(str,input().rstrip()))
f_len=len(f)
s_len=len(s)
dp=[[0]*(s_len+1) for _ in range(f_len+1)]

for i in range(1,f_len+1):
    for j in range(1,s_len+1):
        if f[i-1]==s[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

print(dp[-1][-1])

대단한 분들이 많다..