Longest Common Subsequence

서브태스크 $1$에서는 $A$의 모든 부분 수열을 열거하고, 각각이 $B$의 부분 수열인지 확인할 수 있다. 시간 복잡도는 $O(2^N(N+M))$이다.

전체 문제에서는 $D_{i,j}$를 $A$의 앞 $i$개 원소와 $B$의 앞 $j$개 원소의 최장 공통 부분 수열 길이라고 하자. $D_{0,j}=D_{i,0}=0$이다. $A_i=B_j$이면 $D_{i,j}=D_{i-1,j-1}+1$이고, 그렇지 않으면 $D_{i,j}=\max(D_{i-1,j},D_{i,j-1})$이다.

$D_{N,M}$부터 역추적한다. 현재 두 원소가 같으면 그 원소를 답에 넣고 두 인덱스를 모두 줄인다. 다르면 값이 같은 쪽의 이전 상태로 이동한다. 역추적한 원소를 뒤집으면 정답이다. 값이 같은 이전 상태가 둘이라면 어느 쪽으로 이동해도 된다.

한 케이스의 시간 복잡도와 공간 복잡도는 모두 $O(NM)$이다.

Solution written by GPT6