bj9251 LCS(최장 공통 부분 수열)

최장 공통 부분 수열은 2개의 서로 다른 수열에서 공통 요소를 포함한 가장 긴 수열이다.

 

ex)

X = <A,C,A,Y,K,P>

Y = <C,A,P,C,A,K>

=> 최장 공통 부분 수열 Z = <A,C,A,K>

 

이 알고리즘은 몇개의 근본 아이디어로부터 시작된다.

1. X의 4번째 값 K는 Y의 6번째 값 K와 같다.

이때, (1) Z에는 K가 무조건적으로 들어가고,

(2) Z에서 K를 제외한 A,C,A는 X에서 K를 제외한 A,C,A,Y와 Y에서 K를 제외한 C,A,P,C,A의 최장 공통 부분 수열이 된다.

 

2. X의 Y와 Y의 A가 다르고, Z의 A는 X의 Y와 다르다.

(1) 이때, Z는 그대로 X의 A,C,A 까지와 Y의 C,A,P,C,A까지의 최장 공통 부분 수열인 A,C,A이다.

즉, X와 Y 각각 임의의 인덱스에 있는 값이 다르고, 그 X에서 임의의 인덱스에 있는 값과 Z의 마지막 값이 다르다면, 최장 공통 부분 수열은 X와 Y 각각 임의의 인덱스까지의 최장 공통 부분 수열이라는 뜻이다.

-> Y일때도 똑같다.(현재 검사하는 값이 같지 않다면, 아무리 검사 인덱스가 커져도 최장 공통 부분 수열은 같다는 뜻)

 

이를 요약하자면,

X와 Y의 값이 같을때는 최장 공통 부분 수열을 증가시켜야하고,

X와 Y의 값이 다를때는 최장 공통 부분 수열은 이미 최대이므로 그대로 둔다.

 

이 과정은 DP로 알고리즘을 구현할 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static String X;
    static String Y;
    static int[][] dp;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        X = bufferedReader.readLine();
        Y = bufferedReader.readLine();
        dp = new int[Y.length()+1][X.length()+1];

        int ans = 0;
        for(int i = 1; i <= Y.length(); i++) {
            for(int j = 1; j <= X.length(); j++){
                if(Y.charAt(i-1) == X.charAt(j-1)) {  //임의의 인덱스의 값이 같다면 최장 공통 부분 수열은 그 이전 부분 수열들의 최장 공통 수열을 증가시킨 수열이다..
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ans = Math.max(ans, dp[i][j]);
                }else{  //임의의 인덱스 값이 같지 않다면 최장 공통 부분 수열은 그 이전 최장 공통 수열과 같다.
                    //그 이전이란, X의 j-1, Y의 i,  X의 j, Y의 i-1이 될 수 있다.
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        System.out.println(ans);
    }
}

 

이론을 모른다면, 풀기 어려울 것 같다.