[백준] [9251] LCS

문제

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

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

입력

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

출력

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

 

import java.io.*;

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 n1 = s1.length();
		int n2 = s2.length();
		
		int[][] dp = new int[n1+1][n2+1];
		
		for(int i = 1; i <= n1; i++) {
			for(int j = 1; j <= n2; 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[n1][n2]);
	}
}

최장 공통 부분 수열 즉, LCS(Longest Common Subsequence)는 다이나믹 프로그래밍의 대표적 문제라 할 수 있다.

두 문자열의 겹치는 가장 긴 수열을 구하기 위해 두 문자열의 인덱스가 증가할 수록 가지는 패턴을 이해해야한다.

x = C 일때
y의 인덱스가 증가한다면,

대상이 {C}일때

가장 긴 공통수열의 길이는 다음과 같이 된다.

{A} = 0
{A, C} = 1
{A, C, A} = 1
{A, C, A, Y} = 1
{A, C, A, Y, K} = 1
{A, C, A, Y, K, P} = 1

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

s1.charAt(i)와 s2.charAT(j)이 같다면 dp[i][j] = dp[i-1][j-1] + 1 이다.

대상이 {C, A}일때

가장 긴 공통수열의 길이는 다음과 같이 된다.

{A} = 1
{A, C} = 1
{A, C, A} = 2
{A, C, A, Y} = 2
{A, C, A, Y, K} = 2
{A, C, A, Y, K, P} = 2

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

대상이 {C, A, P}일때

가장 긴 공통수열의 길이는 다음과 같이 된다.

{A} = 1
{A, C} = 1
{A, C, A} = 2
{A, C, A, Y} = 2
{A, C, A, Y, K} = 2
{A, C, A, Y, K, P} = 3

	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
A
K

대상이 {C, A, P, C}일때

가장 긴 공통수열의 길이는 다음과 같이 된다.

{A} = 1
{A, C} = 2
{A, C, A} = 2
{A, C, A, Y} = 2
{A, C, A, Y, K} = 2
{A, C, A, Y, K, P} = 3

	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
K

대상이 {C, A, P, C, A}일때

가장 긴 공통수열의 길이는 다음과 같이 된다.

{A} = 1
{A, C} = 2
{A, C, A} = 3
{A, C, A, Y} = 3
{A, C, A, Y, K} = 3
{A, C, A, Y, K, P} = 3

	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

대상이 {C, A, P, C, A, K}일때

가장 긴 공통수열의 길이는 다음과 같이 된다.

{A} = 1
{A, C} = 2
{A, C, A} = 3
{A, C, A, Y} = 3
{A, C, A, Y, K} = 4
{A, C, A, Y, K, P} = 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.charAt(i)와 s2.charAt(j)이 같다면 dp[i][j] = dp[i-1][j-1] + 1 이고
s1.charAt(i)와 s2.charAt(j)이 다르다면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])이게 된다.


다이나믹 프로그래밍은 인덱스가 증가함에따라 배열의 값이 어떻게 변화하는지 패턴을 식으로 표현할 수 있어야한다.

-새벽코딩-