[BOJ 9251] LCS 최장 공통 부분 수열 문제 (Java)

LCS 문제란?

최장 공통 부분수열 문제는 LCS라고도 불린다.

이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다

 

 

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

 

문제

https://www.acmicpc.net/problem/9251

9251번: LCS

ACAYKP, CAPCAK

두 수열의 LCS(최장 공통 부분 수열)은 ACAK이다. 

 

풀이

도저히 풀이가 생각이 안나서 위키 백과를 참고 했다. 

아래는 LCS의 점화식이다.  

 

 

출처: 위키백과

일단 위 점화식을 토대로 2차 배열을 채워나가면서 LCS의 최대값을 구한다.

 

1. 2차 배열 생성

        String s1 = br.readLine();
        String s2 = br.readLine();

        int n = s1.length();
        int m = s2.length();
        int[][] dp = new int[n+1][m+1];

 

2. i=0, j=0 번째는 0으로 채운다.

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

 

3. 문자 일치 여부에 따라 아래 점화식으로 dp의 값을 채워나간다.

i번째와 j번째 문자가 다를 경우 

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

i번째와 j번째 문자가 일치할 경우

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

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

 

소스코드

package dp;

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

public class BOJ9251 {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();

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

    }
}