[백준] 9251번 : LCS(Longest Common Subsequence)

https://cryosleep.tistory.com/17

LCS란? Longest Common Subsequence=최장 공통 부분순서

그냥 댕쉬움.

문제 풀면서 인지한 동적 프로그래밍, Tabulation의 테이블 작성의 공통점. 정답을 구하기 위해 당장에는 무의미한것까지 맨땅부터 차근차근 다 해보는 것이다(당장에는 무의미하지만 그 무의미한게 답을 구하게 해줌).



두개의 문자열을 비교하는 것이므로 2차원 배열임. x축=문자열A, y축=문자열B
배열은 문자열 각각의 길이에서의 LCS의 길이로 구성됨.

비교되는 2개의 문자열의 타겟 문자가 같으면 dp[i][j]=1+dp[i-1][j-1]

비교되는 2개의 문자열의 타겟 문자가 다르면 dp[i][j]=max(dp[i-1][j], dp[i][j-1]

from sys import stdin
#0-1배낭문제와는 달리 문자열간 비교이므로 어떤 물자열이 X축이고 Y축인지 중요하지 않음
def lcsSolution(a,b):
    x=len(a)
    y=len(b)
    dp=[[0]*(x+1) for _ in range(y+1)]

    for i in range(1, y+1):
        for j in range(1, x+1):
            if(a[j-1]==b[i-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[y][x])



def main():
    a=stdin.readline().strip()
    b=stdin.readline().strip()
    lcsSolution(a,b)

main()