[BOJ] 1958 LCS 3 - JAVA

1. 문제

1958번: LCS 3

문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.

이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.

---

2. 풀이

기본 LCS알고리즘을 3차원으로 확장시키면 바로 해결되는 문제다.

세 문자열의 글자가 모두 같다면 [i-1][j-1][k-1]+1, 다르다면 세 방향 dp의 최댓값을 저장한다.

[LCS 문제] 에 있는 알고리즘 설명과 동일한 방식이므로 설명은 생략한다. (3차원이라 그림 그리기도 어렵다 ^^;ㅎ)

import java.io.*;
import java.util.*;

public class BOJ_1958_LCS3 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      char[] str1 = in.readLine().toCharArray();
      char[] str2 = in.readLine().toCharArray();
      char[] str3 = in.readLine().toCharArray();

      int[][][] lcs = new int[str1.length + 1][str2.length + 1][str3.length + 1];
      for (int i = 1; i <= str1.length; i++) {
         for (int j = 1; j <= str2.length; j++) {
            for (int k = 1; k <= str3.length; k++) {
               if (str1[i - 1] == str2[j - 1] && str2[j - 1] == str3[k - 1]) {
                  lcs[i][j][k] = lcs[i - 1][j - 1][k - 1] + 1;
               } else {
                  lcs[i][j][k] = Math.max(lcs[i - 1][j][k], Math.max(lcs[i][j - 1][k], lcs[i][j][k - 1]));
               }
            }
         }
      }

      System.out.println(lcs[str1.length][str2.length][str3.length]);
   }
}

---

3. 결과