문제
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
Comment