[알고리즘] 백준 9251 파이썬 - LCS

 

9251번: LCS

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

문제풀이

a=input()
b=input()
ans=[0]*1000
#01
for i in range(len(a)):
    tmp=0
    for j in range(len(b)):
    	#02
        if tmp<ans[j]:
            tmp=ans[j]
        #03
        elif a[i]==b[j]:
            ans[j]=tmp+1
print(max(ans))

- #01 : i 값을 모든 j값에 비교하며 값이 같은지 비교하며, 누적으로 값을 올려나갈 것이다.

- #02 : tmp가 ans[j]보다 작은 경우는 바로 일어나지 않는다.

           즉 누적으로 값을 쌓기 위해, 다른 글자의 경우 누적 변수 값이 해당 위치보다 값이 작다면

           그 값을으로 교체해주는 것이다.

- #03 : 만약 같은 글자라면, 그 값에 +1을 해준다.

           최종적으로 가장 큰 ans 값을 출력해준다.

           

출처 : 백준 9251 파이썬 - LCS - 동적 계획법 (tistory.com)