[백준 9251] LCS (python)

9251번: LCS

---

DP로 해결

1. [A길이+1][B길이 +1] 배열을 생성한다.
2. for문을 돌며 하나씩 비교해서 저장한다.
3. 마지막값을 출력한다.

 

※ 비교방법)

만약 ABCD와 DEFC를 비교한다면

 A B  C ,  D E F  C  - 비교할 때 같은 문자라면,  A B  와   D E F  비교값에 1을 더해준다.

 A B  C ,  D E  F  - 비교할 때 다른 문자라면,  A B  C  와  D E  비교값과,  A B 와  D E  F  비교값 중 큰 값을 저장한다.

import sys
input = sys.stdin.readline
A = input().rstrip()
B = input().rstrip()

arr = [[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]:
            arr[i][j] = arr[i-1][j-1]+1
        else:
            arr[i][j] = max(arr[i-1][j], arr[i][j-1])

print(arr[len(A)][len(B)])