139. 9251(LCS)

import sys
input = sys.stdin.readline

A = input().strip()
B = input().strip()

lenA = len(A)+1
lenB = len(B)+1

arr = [[0]*(lenB) for _ in range(lenA)]

for i in range(1,lenA):
    for j in range(1,lenB):
        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[-1][-1])

문제요약

첫번째 문자열과 두번째 문자열의 부분 수열이 되는 것 중 가장 긴 것을 찾아라.

설명

일치하는 문자를 구하라는 문제가 아니라 부분 수열이 되는 수열 중 가장 긴 수열을 구하라는 것이다.

2차원 배열을 이용하여 두 문자열의 문자를 비교하면서 가장 긴 수열을 찾아 나간다.

i를 기준으로 j를 탐색하면서 같으면 1 증가, 같지 않으면 i 전 인덱스, j 전 인덱스 중 큰 값을 갖는다.

순차적으로 증가하면서  배열의 마지막 부분이 가장 큰 길이가 된다.

 

A = input().strip()
B = input().strip()

lenA = len(A)+1
lenB = len(B)+1

arr = [[0]*(lenB) for _ in range(lenA)]

[0]이 안에 들어가는 이유는 J가 B이기 때문이다.

다시한번 말하면 arr[i][j] 에서 J가 B이기 때문에 위와같이 작성해 준다.

 

for i in range(1,lenA):
    for j in range(1,lenB):
        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[-1][-1])

순차적으로 증가시키면서 수열 중 가장 긴 것을 찾는다.