[BOJ] 9251 LCS - DP, 문자열

www.acmicpc.net/problem/9251

9251번: LCS

먼저 두 문자열을 입력받는다. 개행문자 제거를 위해 strip()함수를 사용한다.

두 문자열의 길이만큼 이차원 배열을 만든다.

dp[i][j]를 첫번째 문자열의 i번쨰까지의 부분문자열과 두번째 문자열의 j번째까지의 부분문자열 중 가장 긴 공통부분문자열의 길이로 정의하자.

두 문자열을 하나씩 늘려가면서 부분문자열을 비교해본다. 만약 첫번쨰 문자열의 [i]와 두번째 문자열의 [j]가 같다면

dp[i][j] = dp[i-1][j-1] + 1이 되고, 다르다면 

dp[i][j] = max(dp[i-1][j], dp[i][j-1])이 된다.

import sys
str1 = sys.stdin.readline().strip().upper()
str2 = sys.stdin.readline().strip().upper()
 
len1 = len(str1)
len2 = len(str2)
 
dp = [[0] * (len2+1) for _ in range(len1+1)]
 
for i in range(1, len1+1):
    for j in range(1, len2+1):
        if str1[i-1] == str2[j-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[-1][-1])