[백준/JAVA] 1958번: LCS 3

📖 문제

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

 

 

 

💡  풀이 방식

• LCS

문자열이 3개이므로, 3차원 DP로 LCS 길이를 구하면 된다.

 

- 3중 for문을 이용해 i == j == k인 지점을 찾아 갯수를 센다.

(i, j, k) = max( (i-1, j, k), max( (i, j-1, k), (i, j, k-1) ) )

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[][][] dp;    // 3차원 DP
    static char[] A,B,C;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        A = br.readLine().toCharArray();
        B = br.readLine().toCharArray();
        C = br.readLine().toCharArray();
        
        dp = new int[A.length + 1][B.length + 1][C.length + 1];
        
        LCS();
        System.out.println(dp[A.length][B.length][C.length]);
    }
    
    private static void LCS() {
        for(int i = 1 ; i <= A.length ; i++) {
            for(int j = 1 ; j <= B.length ; j++) {
                for(int k = 1 ; k <= C.length ; k++) {
                    if(A[i-1] == B[j-1] && B[j-1] == C[k-1])
                        dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                    else
                        dp[i][j][k] = Math.max(dp[i-1][j][k], Math.max(dp[i][j-1][k], dp[i][j][k-1]));
                }
            }
        }
    } 
}

 

 

---

💦 어려웠던 점

- 첫 번째 문자열과 두 번째 문자열의 LCS 문자열을 구한 후, 그 결과와 세 번째 문자열의 LCS 길이를 구할 생각을 했었다,,

 

🧐 새로 알게 된 내용

- 그냥 3차원 dp를 쓰면 된다는 점,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준 1958번] LCS 3 (java)