[백준/파이썬][Gold V] LCS - 9251

[Gold V] LCS - 9251

문제 링크

성능 요약

메모리: 118220 KB, 시간: 120 ms

분류

다이나믹 프로그래밍, 문자열

제출 일자

2024년 11월 11일 19:45:55

문제 설명

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

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

입력

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

출력

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

 

풀이

전형적인 LCS 풀이이므로, 다이나믹 프로그래밍을 활용해서 풀이하였다.

text1 = input()
text2 = input()

n, m = len(text1), len(text2)

dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, n + 1) :
    for j in range(1, m + 1) :
        if text1[i-1] == text2[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
        else :
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[n][m])

이 문제를 풀이할 때, 리트코드에 유사한 문제를 풀어본 적이 있어서 생각보다 쉽게 풀이할 수 있었다. 

ACAYKP
CAPCAK

[0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 2, 2, 2]
[0, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 2, 3, 4]
[0, 1, 2, 3, 3, 3, 4]

예제 케이스에 대해서, DP 테이블은 다음과 같이 형성된다.