1958 LCS 3

두 문자열의 LCS가 아닌 세 문자열의 LCS를 구하는 문제이다.

처음엔 단순하게 MIN(LCS(a,b),LCS(b,c),LCS(c,a)) 로 구하려했으나 WA를 받았고..
그 다음으로 생각한게 LCS를 확장하는것이다.

세 문자열의 길이를 각각 p , q , r 이라 할 때,
LCS는 O(pq)의 시간복잡도를 갖지만, 이것을 확장하여 세 문자열로 처리하게끔 하면
O(pqr) 의 시간복잡도를 갖는다. 형식을 똑같이 유지하며 확장시켜주면 답을 구할 수 있다.

소스