[JAVA]백준9252번 LCS2

문제는 다음과 같다.

오늘은 백준9252번 LCS2 문제를 풀어보도록 하자. 위 문제는 Long Common Substring이 아닌 Long Common Subsequence문제이다. 둘 다 LCS이고 DP로 풀이가 가능하다.

기본적인 LCS문제이고 만일 가장 긴 문장을 뽑을 때는 다음과 같은 로직을 거친다.

1. 저장된 dp배열의 오른쪽 아래 구석에서 시작한다.
2. 만일 위의 값과 같으면 위로 이동, 왼쪽 값과 같으면 왼쪽으로 이동, 둘 다 같지 않으면 answer에 문자추가 후 왼쪽 대각선으로 이동
3. 만일 dp배열의 값이 0이면 종료
4. 반대로 추적했기 때문에 문자열 반대로 출력

                                     [코드]
package BaekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_9252 {
    static String answer = "";
    static int num = 1;
    static int dp[][];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String string_1 = br.readLine();
        String string_2 = br.readLine();

        dp = new int[string_1.length()+1][string_2.length()+1];

        for(int i=1;i<=string_1.length();i++){
            for(int j=1;j<=string_2.length();j++){
                if(string_1.charAt(i-1) == string_2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        System.out.println(dp[string_1.length()][string_2.length()]);

        int i = string_1.length();
        int j = string_2.length();

        while(dp[i][j] != 0){
                if(dp[i][j] == dp[i-1][j]){
                    i--;
                }
                else if(dp[i][j] == dp[i][j-1]){
                    j--;
                }
                else{
                    answer+=string_1.charAt(i-1);
                    i--;
                    j--;
                }
        }
        System.out.printf(new StringBuffer(answer).reverse().toString());
    }
}