[백준]#9252 LCS 2

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

예제 입력 1

ACAYKP
CAPCAK

예제 출력 1

4
ACAK

풀이

이 문제는 DP 알고리즘을 이용해서 LCS의 길이를 구한뒤에 역추적으로 해당 수열을 출력해서 풀 수 있다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String A = br.readLine();
        String B = br.readLine();
        int[][] dp = new int[1001][1001];
        String ans = "";

        for(int i=0; i<A.length(); i++) {
            for(int j=0; j<B.length(); j++) {
                if(A.charAt(i)==B.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                }
                else {
                    dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
                }
            }
        }

        int row=A.length();
        int col=B.length();

        while( row>0 && col>0 ) {
            if( dp[row-1][col] == dp[row][col] ) {
                row--;
            }

            else if( dp[row][col] == dp[row][col-1] ) {
                col--;
            }

            else {
                ans = A.charAt(row-1) + ans;
                row--;
                col--;
            }

            if( !(row>0 && col>0) ) {
                if( dp[row][col]!=0 ) {
                    ans = A.charAt(row-1) + ans;
                    if(row>=0)
                        row--;
                    if(col>=0)
                        col--;
                    if(row<0 || col<0)
                        break;
                }
            }
        }

        System.out.println(dp[A.length()][B.length()]);
        System.out.println(ans);
    }
}