⭐⭐⭐⭐[백준][파이썬][DP][LCS] 9252번: LCS2

문제집: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

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

 

이전 문제: LCS https://hyundoil.tistory.com/357

 

LCS 문제 모음 : https://www.acmicpc.net/workbook/view/5080

문제

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

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

입력

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

출력

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

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

예제 입력 1

ACAYKP
CAPCAK

예제 출력 1

4
ACAK

---

 

이전 LCS 문제에서는 저장할 값을 숫자로 DP에 저장하였다. 

def solution(words1,words2):
    
    N=len(words1)
    M=len(words2)
    
    dp = [[0]*(M+1) for _ in range(N+1)]
    
    for i in range(1,N+1):
        for j in range(1,M+1):
            if words1[i-1]==words2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[N][M]
    

if __name__=="__main__":
    words1 = str(input())
    words2 = str(input())
    print(solution(words1,words2))

 

 

이번에는 저장할 값을 숫자 대신 문자를 넣어주면 된다.

그리고 그 문자의 길이를 마지막에 출력하면 따로 숫자 구하고 문자 구하고 할 필요가 없다.

 

def solution(word1, word2):
    N = len(word1)
    M = len(word2)
    
    dp = [['']*(M+1) for _ in range(N+1)]
    
    for i in range(1,N+1):
        for j in range(1,M+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1] + word1[i-1]

            else:
                if len(dp[i-1][j]) > len(dp[i][j-1]):
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
                 
    answer = len(dp[N][M])
    print(answer)
    if answer != 0:
        print(dp[N][M])
    

if __name__=="__main__":
    word1 = str(input())
    word2 = str(input())
    
    solution(word1, word2)