최장 공통 부분 수열 - LCS 백준 9251번

문제

 

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

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


입력

 

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


출력

 

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


예제 입력 예제 출력
ACAYKP
CAPCAK
4

 


해결 방법

 

 

문자열에서 가능한 수열을 모두 만들어 비교하는 방법은  O($2^n$*$2^m$) 으로 매우 느리다.

 

예제 입력을 이용해 DP라는 2차원 배열을 생성해보자.

  A C A Y K P
C 0 1 1 1 1 1
A 1 1 2 2 2 2
P 1 1 2 2 2 3
C 1 2 2 2 2 3
A 2 2 3 3 3 3
K 2 2 3 3 4 4

 

여기서 DP[i][j]는 행에서 현재까지 나온 문자열과 열에서 현재까지 나온 문자열의 부분 공통 수열의 길이를 뜻한다.

 

예를 들어 DP[1][6]는 "ACAYKP"와 "C"의 부분 수열의 최대길이를 나타낸 것이다. 이제 각 행마다 순서대로 값을 채워나가는데, 규칙은 다음과 같다.

 

만약 비교하는 위치의 문자가 서로 같으면 현재 위치의 값= 왼쪽 대각선 값+1 (이전 부분 수열들의 공통 길이의 +1)

 

만약 비교하는 위치의 문자가 서로 다르면 현재 위치의 값= max( 위쪽, 왼쪽) 이다. 

 

package gold;

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

public class P9251 {
	
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		String a=br.readLine();
		String b=br.readLine();
		dp=new int[a.length()+1][b.length()+1];
		
		System.out.println(solve(a,b));
		
	}
	static int solve(String a,String b) {
		int max=-1;
		for(int i=1;i<a.length()+1;i++)
			for(int j=1;j<b.length()+1;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]);
				}
				if(max<dp[i][j])
					max=dp[i][j];
			}
		return max;
	}
}
java