[백준] 9252번 : LCS 2 (JAVA)

1. 문제 분석

 

DP는 자주 풀어도 정말 어려운것 같다.. 전에 풀었던 오름차순 부분수열과 꽤 유사한데 이 문제는 그 수열또한 출력해야 한다.

 

시간복잡도 : O(N^2) 

알고리즘 : DP

2. 문제 풀이

수열의 길이를 1씩 늘려가며 dp에 LCS의 길이를 저장하면서 진행한다.

• i번째와 j번째가 같을 때 : dp[i][j] = dp[i-1][j-1] + 1
• 다를 때 : dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

 

3. 코드 구현

import java.io.IOException;
import java.util.Scanner;

public class BOJ_9252 {

    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        String A = sc.nextLine();
        String B = sc.nextLine();
        int n = A.length();
        int m = B.length();
        int[][] dp = new int[n+1][m+1];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(A.charAt(i-1) == B.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        System.out.println(dp[n][m]);

        StringBuilder lcs = new StringBuilder();
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (A.charAt(i - 1) == B.charAt(j - 1)) {
                lcs.append(A.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        System.out.println(lcs.reverse().toString());


    }
}