[백준]동적 계획법1/LCS/9251 풀이 JAVA

문제

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

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

 

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다.

문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

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

 

풀이(JAVA)

예제인 ACAYKP와 CAPCAK의 LCS 길이를 찾아보자.

 

아래 표는 이차 배열인 dp를 나타낸 것이다.

str1은 ACAYKP, str2는 CAPCAK이다.

str1의 A는 0번째 문자, C는 2번째 문자란 것을 0-A, 1-C << 이렇게 표현했다.

 

dp[3][2]는

str1의 3번째 글자까지인 ACAY와

str2의 2번째 글자까지인 CAP의

LCS길이인 2를 담고있다. ({C, A}로 길이는 2다)

 

dp[1][1]은 AC와 CA의 LCS는 {C}또는 {A}인데 이때는 str1에 먼저 나온 글자로 표를 채웠다.

 

(이때 LCS 길이가 {A, C}로 2라고 생각할 수도 있지만...

str1의 AC의 순서대로 str2의 LCS를 찾기 때문에 하나가 맞다.

예를 들면

예제인 ACAYKP와 CAPCAK도 LCS가 ACAK인데, ACAYKP, CAPCAK 이렇게 str1의 순서대로 찾기 때문에

str1과 str2 모두 P가 들어가지만 순서가 다르기 때문에 잘리는 것이다.)

 

dp[str1][str2]	0-A	1-C	2-A	3-Y	4-K	5P
0-C	0 {}	1 {C}	1 {C}	1 {C}	1 {C}	1 {C}
1-A	1 {A}	1 {C}	2 {C, A}	2 {C, A}	2 {C, A}	2 {C, A}
2-P	1 {A}	1 {C}	2 {C, A}	2 {C, A}	2 {C, A}	3 {C, A, P}
3-C	1 {A}	2 {A, C}	2 {A, C}	2 {A, C}	2 {A, C}	3 {C, A, P}
4-A	1 {A}	2 {A, C}	3 {A, C, A}	3 {A, C, A}	3 {A, C, A}	3 {C, A, P}
5-K	1 {A}	2 {A, C}	3 {A, C, A}	3 {A, C, A}	4 {A, C, A}	4 {A, C, A, K}

 

우리가 구하고자 하는 것은 dp[5][5]이다.

이를 재귀로 표현하는 방법은 아래 코드와 같다.

 

	import java.io.*;
	import java.util.StringTokenizer;
	public class Main {
	static char[] str1; // 입력받을 문자열 1
	static char[] str2; // 입력받을 문자열 2
	static Integer[][] dp; // dp[x][y] = m; str1의 x번째까지의 문자열과 str2의 y번째까지의 문자열의 LCS 길이는 m
	// ex) str1 = ACAYKP, str2 = CAPCAK일 때
	// dp[2][3] = ACA와 CAPC의 LCS 길이는 {A, C}로 2
	// LCS(Longest Common Subsequence, 최장 공통 부분 수열), LCS 길이를 리턴함
	static int LCS(int x, int y) { // LCS(str1의 x번째 글자, str2의 y번째 단어)
	// 인덱스 오류 방지(공집합)
	if (x < 0 || y < 0) return 0;
	// 아직 참색하지 않았다면
	if (dp[x][y] == null) {
	dp[x][y] = 0; // 부분 수열을 0으로 초기화(공통 부분 수열이 0개)
	// str1의 x번째 문자와 str2의 y번째 문자가 같으면(이전 공통 부분 수열 + 1)
	if (str1[x] == str2[y]) dp[x][y] = LCS(x - 1, y - 1) + 1;
	// 같지 않으면
	// str1의 길이를 하나 줄인 LCS 길이와 str2의 길이를 하나 줄인 LCS 길이 중 최댓값으로
	else dp[x][y] = Math.max(LCS(x - 1, y), LCS(x, y - 1));
	}
	return dp[x][y];
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// 두 문자열 입력
	str1 = br.readLine().toCharArray();
	str2 = br.readLine().toCharArray();
	dp = new Integer[str1.length][str2.length];
	// 출력
	System.out.println(LCS(str1.length - 1, str2.length - 1));
	}
	}

view raw Main.java hosted with ❤ by GitHub