[백준 1958번] LCS 3 (java)

1958번: LCS 3

동적 계획법을 통한 최장 공통 수열을 구하는 문제이다.

보통은 두 문자열의 LCS를 구하는데, 이 문제는 세 개의 문자열의 LCS를 구해야 한다.

 

아래는 LCS(Lowest Common Subsequence)를 구하는 방법에 대한 글이다.

lotuslee.tistory.com/39?category=964787

LCS(Longest Common Subsequence)

 

처음에는 먼저 두 문자열의 LCS를 구한 후, 이 문자열과 나머지 한 개의 문자열의 LCS를 다시 구하여 문제를 풀었다.

그런데 계속 '틀렸습니다' 가 떴다.

이런식으로 두 문자열의 LCS을 먼저 구하게 되면, 반례가 생기게 된다.

 

예를 들어, 세 개의 문자열이 다음과 같을 때,

 

s1 : abbbccc
s2 : bbbaddd
s3 : cccddda

 

s1과 s2 문자열의 LCS는 "bbb"이고, "bbb"와 s3 문자열의 LCS는 없다. 즉, 길이가 0이 된다.

s2와 s3 문자열의 LCS는 "ddd"이고, "ddd"와 s1 문자열의 LCS는 없다. 즉, 길이가 0이 된다.

s1과 s3 문자열의 LCS는 "ccc"이고, "ccc"와 s2 문자열의 LCS는 없다. 즉, 길이가 0이 된다.

 

하지만, s1, s2, s3 문자열의 LCS는 "a"가 될 수 있다.

 

따라서 위처럼 두 문자열의 LCS를 우선적으로 구하면 원하는 결과를 얻을 수 없다.

 

이 문제를 해결하기 위해 3차원 배열을 만들어서 LCS를 구하였다.

원래 두 문자열 사이의 LCS를 구하는 코드에서 배열만 2차원에서 3차원으로 변경하고, 로직은 동일하게 하여 문제를 풀었다.

 

 

전체코드 :