[BOJ] 9251 LCS

시간 제한이 2초(사실 0.1초지만 파이썬 농어촌전형으로 2초 줌)
그렇다는 건 최대 1000글자니까 부분 집합 모두 구하는 건 불가능하다는 뜻

빡대가리이기 때문에 DP는 솔직히 답이 없다(2차원 DP 쉣 ㅋㅋ)
열심히 풀이 보긴 봤는데 내가 이해한 바는 다음과 같다

1. 두 문자열 길이가 다를 수 있다
2. 문자열 하나를 이중 리스트로 비교해가면서 있는지 확인
3. NxM에서 문자열 길이를 더해가면서 비교하면 기존에 만들 수 있던 길이보다 +1인지, 최대 길이인지 확인 가능

A = input()
B = input()

matrix = [[0]*(len(B)+1) for _ in range(len(A)+1)]
for i in range(1, len(A)+1):
    for j in range(1, len(B)+1):
        if A[i-1] == B[j-1]:
            matrix[i][j] = matrix[i-1][j-1]+1
        else:
            matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])

print(matrix[-1][-1])