백준 9251: LCS - DP(파이썬)

LCS 성공

9251번: LCS

문제

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

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

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

내 코드

 

import sys

#문자열 str1, str2
str1=list(sys.stdin.readline().rstrip())
str2=list(sys.stdin.readline().rstrip())

#각 문자열의 길이 l1, l2
l1=len(str1)
l2=len(str2)

#가로 0~l1, 세로 0~l2 표 생성
chart=[[0]*(l1+1) for _ in range(l2+1)]

for i in range(1,l2+1): #세로
    for j in range(1, l1+1): #가로

        if str2[i-1]==str1[j-1]: #각 문자열에서 제일 끝에 추가한 문자가 같으면,
            chart[i][j]=1+chart[i-1][j-1] #각각 하나 추가하기전의 문자열에서 +1 한거랑 같다.
        else: #각 문자열에서 제일 끝에 추가한 문자가 다르면,
            chart[i][j]=max(chart[i-1][j],chart[i][j-1]) #하나 이전의 str1과 현재 str2, 하나 이전의 str2와 현재 str1 중 큰값

print(chart[l2][l1]) #chart의 최종 값 출력

 

풀이 및 접근)

- 각 문자열에 대해서 하나씩 문자들을 추가해가면서 비교하는 방식이다.

- 위 코드에서 이중 for문에서, str2가 바깥 for문, str1가 안쪽 for문을 돌고있다. 이러한 구조면, 예제의 경우

str2: C일때 A->C->A->Y->K->P, str2: CA일때 A->C->A->Y->K->P, str2: CAP일때 A->C->A->Y->K->P, .......

이러한 구조이다.

- 이러한 구조에서, 현재 str1의 탐색 문자와 str2의 탐색 문자가 같다면, str1에 하나 추가하기전, str2에 하나 추가하기전 상황의 LCS에서 1을 더한 것이 현재의 LCS 값이 될 것이다.

- 반면에 현재 str1의 탐색 문자와 str2의 탐색 문자가 다르다면, 이 각각의 문자가 str1, str2에 둘다 추가된 상황에서는 의미가 없으므로 현재 str1과 하나 전의 str2의 LCS와, 하나 전의 str1과 현재 str2의 LCS 중 큰 값이 해당 LCS가 될 것이다.