9251 - LCS [DP]

출처 : 백준 9251 LCS

문제

LCS는 최장 공통부분 수열을 의미한다. 문자열 2개가 주어지고 문자열간 공통된 부분중 가장 긴 부분을 찾는 문제이다. 이 때, 연속적인 공통부분을 찾는 것이 아니다. 예를 들어, ACAYKP와 CAPCAKC가 주어지면 ACAK가 최장 공통부분 수열이 되는 것이다.

이 문제는 DP로 문자열 1과 문자열 2를 순회하면서 문자가 같으면 DP 배열에 1을 추가한다. 만약 문자가 다르다면 이전 index중에서 더 큰 값을 받아온다.

풀이

# BOJ 9251 - LCS
import sys
r = sys.stdin.readline

w1 = r().strip() # 행
w2 = r().strip() # 열
lcs = [[0] * (len(w2)+1) for _ in range(len(w1)+1)]

for i in range(1, len(w1)+1):
    for j in range(1, len(w2)+1):
        if w1[i-1] == w2[j-1]:
            lcs[i][j] = lcs[i-1][j-1]+1
        else:
            lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])

print(lcs[-1][-1])
# ACAYKP
# CAPCAKC