[Algorithm] 백준 1958번_LCS3(Java)

🔗 1958번 LCS3

https://www.acmicpc.net/problem/1958

1958번: LCS 3

 

문제

---

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

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

 

입력

---

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

 

출력

---

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

 

📝 접근 방법 및 풀이

---

LCS 접근 방식을 모르겠다면 다음 포스팅을 참고하자.

https://myeongju00.tistory.com/44

[Algorithm] 백준 9251번_LCS(Java)

 

처음에는 먼저 두 문자열의 LCS를 먼저 구한 후 나머지 한 개의 문자열의 LCS를 풀었는데 계속 "틀렸습니다."가 나왔다. 따라서, 3차원 배열을 만들어서 LCS를 구해보았다. 기존의 2차원 배열에서 3차원으로만 변경해서 풀었다.

 

💻 코드

---

 import java.io.*;
 
 public class Main {
     static int[][][] dp;
 
     public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
         char[] str1 = br.readLine().toCharArray();
         char[] str2 = br.readLine().toCharArray();
         char[] str3 = br.readLine().toCharArray();
 
         int length_1 = str1.length;
         int length_2 = str2.length;
         int length_3 = str3.length;
 
         dp = new int[length_1 + 1][length_2 + 1][length_3 + 1];
 
         for(int i = 1; i <= length_1; i++) {
             for(int j = 1; j <= length_2; j++) {
                 for (int k = 1; k <= length_3; k++) {
                     // (i-1)번째 문자 == (j-1)번째 문자 == (k-1)번째 문자
                     if(str1[i - 1] == str2[j - 1] && str2[j - 1] == str3[k - 1]) {
                         dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
                     } 
                     else {
                         //이전 열(i-1)과 이전 행(j-1), (k-1)의 값 중 큰 것으로 갱신
                         dp[i][j][k] = Math.max(dp[i - 1][j][k],
                                 Math.max(dp[i][j - 1][k], dp[i][j][k - 1])
                         );
                     }
                     
                 }
             }
         }
         System.out.println(dp[length_1][length_2][length_3]);
     }
 }