LCS-최장 공통 부분 수열(백준 9251번 파이썬)

예전에 잠깐 봤던 개념인데 다시 보니까 전혀 모르겠어... 다른 사람들 코드 보고 나서야 겨우 이해했다 ㅠㅠ 어려우

풀이

필요요소
1. 입력받은 값을 저장할 두 1차원 배열
2. 이전까지 같은 값이 얼마나 있었는지 저장해줄 1차원 배열
3. 비교할 문자 전까지 얼만큼 같은 문자들이 있었는지 알려줄 변수

로직 순서
1. 입력받은 문자열 두개를 각각의 리스트에 담아준다.
2. 두 문자열을로 이중 for문을 돌려준다.
(바깥 문자열을 A, 안을 B라 하면)
3. 바깥 for문 시작할 때마다 tmp를 0으로 설정해준다.
3. A[i]와 B[j] 값이 같으면 dp[j] 값을 하나 올려주고
4. A[i+1] B[j] 가 됐을 때 tmp가 dp[j]보다 작으면 tmp값을 dp[j]만큼 올려준다.
5. dp에서 최고값 출력

코드

from sys import stdin

A= list(stdin.readline().rstrip())
B= list(stdin.readline().rstrip())

dp = [0]*len(A )
for  i in range(len(B)):
    tmp = 0
    for j in range(len(A)):
        if dp[j]> tmp:
            tmp +=1
        elif B[i] == A[j]:
            dp[j] = tmp +1

print(max(dp))