백준 9251번 : 최장공통부분수열 LCS

정말 암담했다. 아무리 생각해도 풀이법이 생각나질 않아서 구글링을 해보았다. 그거마저 이해하는데 시간이 들었다.

풀이법은 다음과 같았다. 먼저 이차원 리스트를 생각한다.

행과 열을 각문자열을 넣고 하나씩 늘려가며 횡단한다.

예를들어 2행 3열에서 서로 A로 일치하게 된다. 이러면 이 행렬이 추가되기 이전의 값 (1행2열) = 1 에서 1을 더해준다.

이 말은 곧 원래 만들 수 있던 최장공통부분수열 뒤에 A를 하나 더 붙여 길이가 1늘어나게 되었다는 뜻이다.

C -> CA

 

2행 4열은 서로 일치하지 않으므로 좌측값 또는 위에값 중 큰 값인 2를 그대로 가져온다. 이 말은 곧 이 행렬 상관 없이 그 전에 만들 수 있던 것 중 가장 긴 것을 가져오겠다는 뜻이다. 여기서는 CA를 그대로 가져온다는 뜻이다.

이해하기 쉽게 숫자 옆에 만들어지는 최장공통부분수열을 적어서 전체표를 만들어봤다.

5행3열에서는 A로 서로 일치하므로 4행2열 AC에 A를 붙여서 ACA가 최장공통부분수열이 된다.

 

6행2열에서는 서로 일치하지 않으므로 CAPCA와 AC로 만들 수 있었던 최장공통부분수열인 위에 있던 AC를 그대로 가져온다. 

 

이제 감이 올 거라고 생각한다.