[DP] BOJ 9251 LCS

문제

9251번: LCS

 

풀이

1. 인덱스를 수월하게 사용하기 위해 더미 문자열을 입력 문자열 앞에 추가한다.

2. 이중 for를 돌면서 각 문자를 서로 비교한다. DP 테이블에는 현재까지 만들 수 있는 공통 부분 수열의 개수를 넣는다.

 2-1. 만약 i위치와 j위치에서 두 문자가 같다면 [i-1][j-1]에 값에 1을 더한다.

(두 문자열의 각각 이전 문자까지의 공통 문자열 길이에 현재 문자를 더한 것이다. )

 2-2. 만약 i위치와 j위치에서 두 문자가 다르다면 서로 이전의 값 중에서 큰값을 넣는다. 

(두 문자열에 대해서 이전 값을 유지하는 과정)

 

3. 2번을 반복한다.

 

다른 케이스의 예

 

코드

import sys

line1 = '.' + sys.stdin.readline().rstrip()
line2 = '.' + sys.stdin.readline().rstrip()

len1 = len(line1)
len2 = len(line2) 

d = [[0] * len(line1) for _ in range(len(line2))]

for i in range(1,len1):
    for j in range(1,len2):
        if line1[i] == line2[j]: #2-1
            d[j][i] = d[j-1][i-1]+1
        else: #2-2
            d[j][i] = max(d[j][i-1],d[j-1][i])

print(d[len2-1][len1-1])