[백준 9251번] LCS (java)

사용한 방법 : DP

 

2차원 배열을 이용하여 lcs를 구하였다. 예를 들어 dp[i][j]이면,

첫번째 문자열에서 i번까지의 문자열과 두번째 문자열에서 j번까지의 문자열의 LCS를 구한 값이 들어가게 된다.

 

먼저 예시로 주어진 ACAYKP와 CAPCAK로 LCS를 구해보면

 

	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	1	2	3	3	3	3
K	1	2	3	3	4	4

다음과 같이 표를 완성할 수 있다.

여기서 나타나는 규칙을 보면 같은 문자가 만나는 지점에서 값이 증가한다는 점이다.

 

	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	1	2	3	3	3	3
K	1	2	3	3	4	4

첫번째 문자열을 s1, 두번째 문자열을 s2라고 한다면

 

s1의 i번째 문자와 s2의 j번째 문자가 같은 문자일 때(s1.charAt(i) == s2.charAt(j)) :

s1의 i-1번째까지의 문자열과 s2의 j-1번째까지의 문자열간의 LCS에서 +1이 증가가 된다.

dp[i][j]=dp[i-1][j-1]+1

왜냐하면 s1의 i-1번째까지의 문자열과 s2의 j-1번째까지읨 문자열간의 공통 부분 수열의 길이가 n일때,

s1의 i번째 문자와 s2의 j번째 문자가 동일하면 그 전까지의 공통 부분 수열 + 공통의 문자 하나가 더 추가되는 것이기 때문이다.

 

s1의 i번째 문자와 s2의 j번째 문자가 같은 문자가 아닐 때(s1.charAt(i) != s2.charAt(j)) : 

dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])

 

 

전체코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String s1 = br.readLine();
		String s2 = br.readLine();
		int[][] dp = new int[1001][1001];

		for (int i = 1; i <= s2.length(); i++) {
			char c2 = s2.charAt(i - 1);

			for (int j = 1; j <= s1.length(); j++) {
				char c1 = s1.charAt(j - 1);

				if (c1 == c2) {
					dp[i][j] = dp[i - 1][j - 1] + 1;

				} else
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
			}
		}

		bw.write(dp[s2.length()][s1.length()] + "\n");
		bw.flush();

	}
}