백준 9251. LCS

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

M = input()
N = input()

dp = [[0 for _ in range(len(N)+1)] for _ in range(len(M)+1)]

for i in range(1, len(M)+1): # 직전의 문자 비교를 위해 1로 시작
    for j in range(1, len(N)+1):
        if M[i-1] == N[j-1]: # 직전의 문자가 같다면
            dp[i][j] = dp[i-1][j-1] +1 # 현재의 dp값을 직전 dp값 + 1(공통점을 찾았다! = 부분수열로 만들 수 있다)
        else: # 직전의 문자가 다르다면 끊기므로 이전값 그대로 가져오기...
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]) # 현재 문자를 빼고 생각했을 때 최댓값

print(dp[len(M)][len(N)])

# 여기서 dp는 가장 긴 부분수열의 길이만을 저장함
# 모든 부분을 다 탐색했을 때 -> dp[len(M)][len(N)] 저장되어있는 값 = 정답