[백준] 9251번 - LCS

📩 출처

문제

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

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

입력

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

출력

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

👉 생각

• 2개의 문자열에서 LCS를 찾기 위해 먼저 이차원 배열을 만들고 각각의 값을 점화식을 세워 값을 구하는 dp로 접근하였다.

• (A, C), (A, CA), (A, CAP), (A, CAPC), (A, CAPCA), (A, CPACAK)와 같이 한 행에서 A와 문자열들을 비교한다.
• (AC, C), (AC, CA), (AC, CAP), (AC, CAPC), (AC, CAPCA), (AC, CPACAK)와 같이 그 다음 행은 AC와 문자열을 비교한다.
• 각각의 문자열을 stack1과 stack2에 넣고 마지막 문자를 비교한다. 마지막 문자가 같다면 점화식이 다음과 같이 세워진다

dp[i][j] = dp[i-1][j-1]

• stack1과 stack2의 마지막 문자열이 다르다면 dp[i-1][j]와 dp[i][j-1] 중 큰 값을 선택한다.

s1 = input()
s2 = input()

dp = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]
stack1 = []
for i in range(1, len(s1)+1):
    stack1.append(s1[i-1])
    stack2 = []
    for j in range(1, len(s2)+1):
        stack2.append(s2[j-1])
        if stack1[-1] == stack2[-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[-1][-1])