[Java] 백준 9251번: LCS

[문제 바로 가기] - LCS

📌 유형 : dp

이 문제는 LCS(Longest Common Subsequence), 즉 최장 공통 부분 수열 문제로 개념은 여기에서 이해했다.

💡 아이디어

ACAYKP
CAPCAK

LCS는 두 수열이 주어졌을 때 가장 긴 공통 부분 수열을 구하면 되는데 이 문제에서는 위와 같이 문자열로 주어졌다.

예제를 바탕으로 문자열 s1과 s2를 비교해보는 표를 작성했다. s1를 기준으로 문자 하나씩 비교해보도록 하겠다.

1. A와 CAPCAK 비교

	A	C	A	Y	K	P
C	0
A	1
P	1
C	1
A	1
K	1

여기서 두번째 A가 나왔을 때 2가 되는거 아닌가 했지만 A와 비교했을 때 두번째 A도 길이가 1이 될 수 밖에 없다. CAPCAK의 [A]와 ACAYKP의 [A]를 비교하는 것이기 때문에!

2. AC와 CAPCAK 비교

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

ACAYKP의 [A, C]와 CAPCAK의 [A, C]가 일치하기 때문에 두번째 C에서 +1을 한다.

3. ACA와 CAPCAK 비교

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

ACAYKP의 [A, C, A]와 CAPCAK의 [A, C, A]가 일치하기 때문에 두번째 A에서 +1을 한다.

4. ACAYK와 CAPCAK 비교

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

ACAY는 ACA와 큰 차이가 없어 생략했다.
ACAYKP의 [A, C, A, K]와 CAPCAK의 [A, C, A, K]가 일치하기 때문에 K에서 +1을 한다.

5. ACAYKP와 CAPCAK 비교

	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의 문자가 같을 때 (행의 인덱스 - 1)(열의 인덱스 - 1)의 값에 +1을 하고, 같지 않을 경우엔 (행의 인덱스 - 1) 또는 (열의 인덱스 - 1) 중 큰 값을 선택한다.

즉, 2차원 dp 배열을 사용하여 가장 긴 공통 부분 수열을 저장해가면 되는 것이다.

	for (int i = 1; i <= len1; i++) {
		for (int j = 1; j <= len2; j++) {
			if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			} else {
				dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
			}
		}
	}

---

풀이

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

/**
 * 백준 9251번 LCS
 * - dp
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s1 = br.readLine();
		String s2 = br.readLine();
		
		int len1 = s1.length();
		int len2 = s2.length();
		int[][] dp = new int[len1 + 1][len2 + 1];
		
		for (int i = 1; i <= len1; i++) {
			for (int j = 1; j <= len2; j++) {
				if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
				}
			}
		}

		System.out.println(dp[len1][len2]);
	}
}