[BOJ] 백준 9251 LCS

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

 Input 
ACAYKP
CAPCAK

 Output 

4　

LCS의 길이만 출력하는 문제이다

LCS (Longest Common Subsequence) 알고리즘

LCS(Longest Common Subsequence) 알고리즘

---

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();
         
        int[][] LCS = new int[A.length+1][B.length+1];
         
        for(int i=1; i<=A.length; i++) {
            for(int j=1; j<=B.length; j++) {
                 
                if(A[i-1] == B[j-1]) {
                    LCS[i][j] = LCS[i-1][j-1] + 1;
                }
                else {
                    LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
                }
            }
        }
         
        System.out.println(LCS[A.length][B.length]);
    }
}