boj.kr/9251 LCS (gold5) 파이썬 풀이

1. 문자열 A, B를 저장

2. 문자열 B의 길이만큼 dp 배열을 0으로 초기화

3. A 문자열을 순회하면서 아래를 반복

3.1. cnt 변수를 0 으로 초기화

3.2. B 문자열을 순회하면서 아래를 반복

3.2.1. cnt가 dp[bi] 보다 작으면, cnt에 dp[bi]값을 저장

3.2.2. A[ai] 값과 B[bi] 값이 같으면, dp[bi] 값에 cnt+1 값을 저장

4. dp에서 최대값을 출력

 

A = input()
B = input()

dp = [0 for _ in range(len(B))]

for ai in range(len(A)):
    cnt = 0
    for bi in range(len(B)):
        if cnt < dp[bi]:
            cnt = dp[bi]
        elif A[ai] == B[bi]:
            dp[bi] = cnt + 1

print(max(dp))

 

dp[bi]를 B문자열을 bi번째 문자까지 검사했을 때 A문자열과 일치하는 문자 개수의 최대값으로 저장할 수 있다.