백준 5582 java : DP, LCS

참고 : https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

LCS를 사용한 문제풀이다.
LCS 자체를 구할 필요는 없고 최대 길이만 얻으면 되지만 LCS를 구하라는 문제를 대비해야 한다.

import java.util.Scanner;

public class bj5582 {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {

        String A, B;
        A = sc.next();
        B = sc.next();
        System.out.println(findAnswer(A, B));

        sc.close();
    }

    public static int findAnswer(String A, String B) {
        System.out.println("findAnswer()");
        int answer = 0;
        int ALength = A.length();
        int BLength = B.length();
        int [][] DP = new int[ALength+1][BLength+1];
        int i, j;

        // LCS : 최장 공통 부분수열 알고리즘
        System.out.print("  ");
        for(i = 0; i < BLength; i++) {
            System.out.print(B.charAt(i) + " ");
        }
        System.out.println();
        for(i = 1; i <= ALength; i++) {
            System.out.print(A.charAt(i-1) + " ");
            for(j = 1; j <= BLength; j++) {
                if(A.charAt(i-1) == B.charAt(j-1)) {//공통문자이면
                    DP[i][j] = DP[i-1][j-1] + 1;//이전 공통문자열 길이 + 1
                }
                else{//공통문자가 아니면
                    DP[i][j] = 0;//최장 공통 문자열이 끊김
                }

                //최대값 찾으면 갱신
                answer = Math.max(answer, DP[i][j]);

                System.out.print(DP[i][j] + " ");
            }
            System.out.println();
        }

        return answer;
    }
}