#158 백준 파이썬 [9251] LCS

https://www.acmicpc.net/problem/9251

 

 

#Solution

 

https://twinw.tistory.com/126 참조.

두 문자열의 LCS(Longest Common Subsequence)를 찾는 알고리즘은 2차원 배열로 정답을 구할 수 있다.

아래와 같은 알고리즘으로 푼다.

 

1) 각 문자열 길이에 1을 더한 값을 X축, Y축으로 두고 0을 대입한다.

2) A[i]와 B[j]가 같은 arr[j][i]자리의 값은 위 혹은 왼쪽 중 큰 값을 대입해준다.

- A의 시작부터 본 값 or B의 시작부터 대입한 값 중 제일 긴 것이 들어가는 것

3) A[i]와 B[j]가 같은 arr[j][i]자리의 값은 대각선 왼쪽 위의 값에 +1 해준 값을 대입해준다.

- 위나 왼쪽이 아닌이유?: 같은 값이 위 예시에서 K라면, A_case: ACA_ +K / B_case: _A_CA +K 와 같이 각각 이전의 값에 더해주어야하기 때문이다.

A = list(str(input()))
B = list(str(input()))
            
#배열 생성
arr = [[0 for _ in range(len(A) + 1)] for _ in range(len(B) + 1)]
answer = 0


#규칙에 따라 순차적으로 숫자를 넣어준다.
for i in range(len(A)):
    for j in range(len(B)):
        if A[i] == B[j]:
            arr[j+1][i+1] = arr[j][i] + 1
            answer = max(answer, arr[j+1][i+1])
        else:
            arr[j+1][i+1] = max(arr[j][i+1], arr[j+1][i])

print(answer)