[백준 9251] LCS

[BanApp]

arr1 = list(input())
arr2 = list(input())

tmp = [[0]*(len(arr2)+1) for _ in range((len(arr1))+1)]

for i in range(len(arr1)):
    for j in range(len(arr2)):
        if arr1[i] == arr2[j]:
            tmp[i+1][j+1] = tmp[i][j] +1
        else:
            if tmp[i][j+1] >= tmp[i+1][j]:
                tmp[i+1][j+1] = tmp[i][j+1]

            elif tmp[i][j+1] < tmp[i+1][j]:
                tmp[i+1][j+1] = tmp[i+1][j]

print(tmp[len(arr1)][len(arr2)])

아이디어는 우선 두개의 리스트의 원소를 각각 비교해주는것은 불피하다.
따라서 시간복잡도는 O(NM)이다.
우선 arr1[I] == arr2[j]를 만족하면 대각선 밑에 있는것을 1 증가 시킨다.
왜그러냐면 조합상 arr[0][0] ~ arr[i+1][j+1] 사이에서 만들 수 있는 가장 긴 LCS 크기는 위 조건을 만족할때 arr[i][j] + 1 이기 때문이다.
원소가 같지 않을때는 arr[i-1][j] 와 arr[I][j-1] 중 더 큰것으로 한다.
이 과정에서 인덱스 에러를 피하기 위해서 0으로 이차원 리스트의 왼쪽과 상단을 0으로 감싸준다.
이를 반복하면 가장 오른쪽 최하단에 있는 숫자가 두개의 리스트에서 만들어 질 수 있는 가장 긴 LCS의 값이 나온다.

이런식으로 말이다.

사실 뭔가 수학적으로 이해했기 보다는 직접 그려서 규칙을 찾는 식으로 진행했다.
아이디어만 떠올리면 쉽지만 그게 어려운 DP...
그래도 DP문제는 어떻게든 이전 값을 써먹으려는 방향으로 점화식을 고민하다보면 결국 답은 나온다.