백준 #9252 - [G4] LCS 2 : DP

(python3)

9252번: LCS 2

 

LCS 문제

유명한 DP 유형이라 따로 정리해보았습니다.

LCS (Longest Common Subsequence, 최장 공통 부분 수열)

 

파이썬 코드

import sys
def solution(input) :
    str1 = '_'+input().strip() # 코딩 편의성을 위해 앞에 더미 문자 하나 패딩
    str2 = '_'+input().strip()

    DP = [[0 for _ in range(len(str2))] for _ in range(len(str1))]
	
    # DP 채우기
    for i1 in range(1,len(str1)) :
        for i2 in range(1,len(str2)) :
            if str1[i1] == str2[i2] :
                DP[i1][i2] = DP[i1-1][i2-1] + 1
            else :
                DP[i1][i2] = max(DP[i1-1][i2], DP[i1][i2-1])
    
    # LCS 찾기
    result = []
    i1 = len(str1)-1
    i2 = len(str2)-1

    print(DP[i1][i2]) # LCS 길이 출력

    while True :
        if DP[i1][i2] == 0 : break
            
        if DP[i1][i2-1] == DP[i1][i2] :
            i2-=1
            
        elif DP[i1-1][i2] == DP[i1][i2] :
            i1-=1

        else :
            result.append(str1[i1])
            i1-=1
            i2-=1
    
    result.reverse()
    print(''.join(result))
        
input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac