[BOJ] 백준 1958 LCS 3

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

 Input 

abcdefghijklmn

bdefg

efg

　 

 Output 

3

두 문자열을 입력받아 LCS를 출력하는 문제

LCS (Longest Common Subsequence) 알고리즘

LCS(Longest Common Subsequence) 알고리즘

3개의 문자열에서 LCS를 출력하는 문제로 3차원 배열을 활용하여 해결

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        char[] A = sc.next().toCharArray();
        char[] B = sc.next().toCharArray();
        char[] C = sc.next().toCharArray();
         
        int[][][] LCS = new int[A.length+1][B.length+1][C.length+1];
         
        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] && A[i-1] == C[k-1]) {
                        LCS[i][j][k] = LCS[i-1][j-1][k-1] + 1;
                    }
                    else {
                        if (LCS[i - 1][j][k] > LCS[i][j - 1][k] 
                            || LCS[i - 1][j][k] > LCS[i][j][k - 1])
                                LCS[i][j][k] = LCS[i - 1][j][k];
 
                        else if (LCS[i][j][k - 1] > LCS[i - 1][j][k] 
                            || LCS[i][j][k - 1] > LCS[i][j - 1][k])
                            LCS[i][j][k] = LCS[i][j][k - 1];
 
                        else 
                            LCS[i][j][k] = LCS[i][j - 1][k];
                    }   
                }               
            }
        }
        // 정답 출력
        System.out.println(LCS[A.length][B.length][C.length]);
    }
}