[Python/BOJ] 9252. LCS 2

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

9252번: LCS 2

문제

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

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

입력

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

출력

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

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

풀이

Code

import sys
input = sys.stdin.readline

def solution(s1, s2) :
    l1, l2 = len(s1), len(s2)
    # 1. DP 생성
    dp = [[[0, ''] for _ in range(l2)] for _ in range(l1)]
    # 2.
    for i in range(1, l1) :
        for j in range(1, l2) :
            # 2-1. 두 문자가 같을 경우
            if s1[i] == s2[j] :
                # 점화식에 따라 처리
                dp[i][j][0] = dp[i-1][j-1][0] + 1
                # 문자 추가
                dp[i][j][1] = dp[i-1][j-1][1] + s1[i]
            # 2-2. 두 문자가 다른 경우
            else :
                # 점화식에 따라 처리
                dp[i][j] = dp[i-1][j] if dp[i-1][j][0] > dp[i][j-1][0] else dp[i][j-1]
    # 3. 결과 출력
    print(f'{dp[-1][-1][0]}\n{dp[-1][-1][1]}')
if __name__ == "__main__" :
    s1, s2 = " " + input().rstrip(), " " + input().rstrip()
    solution(s1, s2)