[백준/JAVA] 9251: LCS

[백준/JAVA] 9251: LCS

LCS란 Longest Common Susequence(최장 공통 부분 문자열)의 약자로, common sequence들 중 가장 긴 것을 뜻한다.

예를 들어 ACAYKP와 CAPCAK의 LCS는 ACAK이다. 이때 부분 문자열들이 서로 떨어져 있는 것은 상관이 없지만 문자열에서의 순서는 그대로여야 한다.

어떤 문제를 DP로 풀수 있느냐 없느냐에 대해서는 최적해의 부분또한 그 부분의 최적해인가에 대해 생각해보며 알 수 있다.

문자열 $x$와 $y$가 있을 때 그 둘의 LCS인 $z$가 있고, $z$의 맨 끝 문자는 $'A'$라고 가정한다.

$x$와 $y$에서 $'A'$가 있는 부분을 포함하여 그 뒤의 문자열을 제거하면 $'A'$가 제거된 $z$는 $x'$와 $y'$의 LCS이다. 즉 최적해의 부분또한 최적해라는 조건을 만족한다.

두 문자열을 문자열 배열로 보고, $L[i, j]$를 $x$와 $y$의 LCS의 길이라고 한다면

1. 각 문자열의 맨 끝이 같을 경우
   $L[i-1,j-1]$ (이전값)에 마지막 문자의 길이 $+1$만 해주면 된다.

2. 각 문자열의 맨 끝 문자가 같지 않을 경우
   $L[i-1,j]$와 $L[i,j-1]$ (각각의 이전값) 중에서 더 큰 값을 $L[i,j]$에 대입하여 $x$와 $y$ 중 문자열 하나의 마지막 문자를 버린다.

즉 순환식은 다음과 같다.

위 원리를 이용하여 bottom up 방식으로 함수를 작성하면 문제의 해답을 얻을 수 있다.

소스코드

---

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        int m = str1.length();
        int n = str2.length();
        int dp[][] = new int[m+1][n+1];
        
        for (int i=1; i<=m; i++)
        	for (int j=1; j<=n; j++) {
        		if (str1.charAt(i-1) == str2.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[m][n]);
    }
}

참고자료
https://youtu.be/EtGqdy-9w9M