[백준] LCS (9251번) - Python

문제

https://www.acmicpc.net/problem/9251

아이디어

• DP
• 입력 앞에 문자 하나를 추가해서 마진 생성
• 두 문자열의 길이가 같다는 조건이 없으므로 각각 따로 체크

코드

seq1 = input()
seq2 = input()


# 마진 설정해주기
seq1 = ' ' + seq1
seq2 = ' ' + seq2

lcs = [[0] * len(seq2) for _ in range(len(seq1))]


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


print(lcs[-1][-1])