[Python] 백준 9252번 - LCS 2 (골드 4)

혼자 힘으로 풀었는가? ..?

알고리즘 분류
 - 다이나믹 프로그래밍 (DP)

 

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

 

문제

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

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

입력

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

출력

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

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

 

---

 

2023.08.17 - [Algorithm/백준] - [Python] 백준 9251번 - LCS (골드5)

[Python] 백준 9251번 - LCS (골드5)

 

 

해당문제와 거의 같은 문제였다.

푸는 방식은 동일하며 문자를 저장하기위한 배열을 하나 더 추가하였다.

 

import sys
input = sys.stdin.readline

s1 = input().rstrip()
s2 = input().rstrip()

dp_num = [[0 for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]
dp_char = [['' for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]

for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        if s1[i-1] == s2[j-1]:
            dp_num[i][j] = dp_num[i-1][j-1]+1
            dp_char[i][j] = dp_char[i-1][j-1] + s1[i-1]
        else:
            if dp_num[i-1][j] < dp_num[i][j-1]:
                dp_num[i][j] = dp_num[i][j-1]
                dp_char[i][j] = dp_char[i][j-1]
            else:
                dp_num[i][j] = dp_num[i-1][j]
                dp_char[i][j] = dp_char[i-1][j]
                
if dp_num[len(s1)][len(s2)] == 0:
    print(0)
else:
    print(dp_num[len(s1)][len(s2)])
    print(dp_char[len(s1)][len(s2)])

 

예제결과를 dp로 보여주면 다음과 같다.