9251:LCS [백준 문제풀이][Python][CLASS 4]

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

난이도: 골드 5

LCS(Longest Common Subsequence, 최장 공통 부분 수열)를 찾으면 되는 문제이다. DP를 쓰는 방법에 있어서 꽤 애를 먹었다.

아이디어1

처음 생각했던 풀이는 배낭 문제에서 영감을 얻어 두 번째 리스트에서 각 문자열마다 가질 수 있는 최장 부분 문자열을 저장해주는 것이었다. 이중 for문을 사용해서 같은 문자열이 나오면 그 전 값 중에서 최댓값을 찾아 +1 해주는 식으로 코드를 짜봤다. 아래는 모식도이다.

입력:
ACAYKP
CAPCAK

시도1

n=input()
m=input()
l=[0]*len(n)
for i in n:
    t=l[:]
    for j in range(len(m)):
        if i==m[j]:
            t[j]=max(l[0:j+1])+1
    l=t[:]
print(max(l))

실패한 이유

결과는 93%(...)에서 시간초과. 이유는 최댓값을 찾는 과정에서 max()를 사용함으로써 불필요한 탐색이 추가로 필요해지기 때문이다. 이를 방지하기 위해 cnt라는 변수를 만들어 만약 탐색 중 윗 문자열과 아랫 문자열이 같으면 cnt+=1 해주는 방식으로  그때그때 최댓값을 갱신해주고 불러오는 방식으로 변경하였다.  

정답 코드

a=input()
b=input()
l=[0]*len(b)
for i in range(len(a)):
    cnt=0
    for j in range(len(b)):
        if cnt< l[j]:cnt=l[j]
        elif a[i]==b[j]:l[j]=cnt+1#최댓값 갱신
print(max(l))