이 문제의 경우 주어진 단어의 길이는 1000글자이지만 주어진 시간은 pypy3의 경우 1.5초밖에 주어지지 않았다.
따라서 이중포문을 한 번 돌아서 문제의 답을 유추할 수 있어야했다. 동적계획법을 이용해보자라는 생각이 들었다.
문자열 간의 부분수열을 비교하기 위해서 2차원 테이블 형태로 데이터를 처리해야한다.
{ A, C, D, E, B }와 { B, C, D, E, A }를 이용해 테이블을 채우자.
위 테이블에서 파란색 셀의 0이 의미하는것은 {B} 와 {A}의 LCS의 길이이다.( = 0)
위 테이블에서 파란색 셀의 0이 의미하는것은 {B} 와 {A,C}의 LCS의 길이이다.( = 0 )
위 테이블에서 파란색이 의미하는 것은 {B}와 {A,C,D,E,B}의 LCS의 길이이다. ( = 1 )
위 테이블에서 파란색 셀이 의미하는것은 {B,C,D} 와 {A,C,D}의 LCS의 길이다. ( = 2 )
이런 테이블을 몇개 그리다 보면 규칙이 보인다.
초록색 셀끼리 비교할때 문자가 서로 다르다면 파란색 셀에는 왼쪽값과 윗쪽 값을 비교해서 그냥 큰 수를 쓰면 된다.
-
위 테이블에서 의미하는 파란색 셀의 윗쪽 값은 {B,C} 와 { A,C,D,E }의 LCS 길이이다.( = 1 )
-
위 테이블에서 의미하는 파라색 셀의 왼쪽 값은 {B,C,D}와 {A,C,D}의 LCS 길이이다.( = 2 )
-
따라서 파란색 셀은 길이가 더 긴 왼쪽값을 선택함으로써 {B,C,D}와 {A,C,D,E}의 LCS 길이를 가지게 된다( = 2 )
초록색 셀끼리 비교할때 문자가 서로 같다면 파란색 셀에는 왼쪽 위 대각선의 값에 +1을 해주면된다.
파란색 셀에 {B,C,D,E} 와 {A,C,D,E}의 LCS 길이인 3을 기록한다.
이런식으로 하면 LCS의 길이를 구할 수 있다.
