BOJ 9251: LCS [Python 3]

Dynamic Programming 문제인 LCS이다.

굉장히 웰-노운 문제인 것 같은데, 아이디어를 떠올리기 힘들었다.

극한의 시간 제한 때문에, 일반적인 반복문으로 구할 수 없었다.

 

내가 사용한 DP 알고리즘은 다음과 같다.

우선 모든 칸을 0으로 채우고,

만약 두 문자열에서 같은 문자가 나오면, 

'해당 문자 전까지 찾았던 문자열의 공통 부분'에서 1을 더해준다.

예시를 들면,

ACA와 CA가 겹치는 부분을 보자. (좌표  (3,2))

 

AC까지와 C까지 겹치는 부분이 1이였다. ('C')

근데 이제 

ACA와 CA가 겹치기 때문에, 

AC까지와 C까지 겹치는 부분인 1에 1을 더한다.

('ACA와 CA'가 겹치는 부분이 2니까...!)

 

만약 두 문자가 같지 않다면, 전까지 비교했을 때 중에서 더 겹치는 부분이 많은 부분을 고른다. (한마디로, 위나 왼쪽에서 큰 값을 대입한다.)

 

코드는 다음과 같다.

a=input()
b=input()
lena=len(a)
lenb=len(b)
i=0
dp=[[0 for _ in range(lenb+1)] for _ in range(lena+1)]

for i in range(lena):
    for j in range(lenb):
        if a[i]==b[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else: 
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
print(dp[lena][lenb])