[Baekjoon Online Judge] 9251번: LCS

9251번: LCS

LCS (Longest Common Subsequence)

 

 공통 부분 수열 중 가장 길이가 긴 것이 바로 최장 공통 부분 수열이다. 문제의 예시를 들어보았다.

 

문자열 A - ACAYKP

문자열 B - CAPCAK

 

 두개의 문자열이 있다고 가정하자. 두 문자열의 공통 부분 수열은 C, CA, ACA, ACAK, AA 등이 있다. 그중 가장 긴 부분 수열을 구하는 문제이다.

 

문자열 A - ACAYKP

문자열 B - CAPCAK

 

 이렇게 ACAK가 가장 긴 부분 수열이 된다. 

 

LCS의 길이를 구하는 공식은 생각보다 간단하다. 이 공식과 동적 프로그래밍을 사용하여 문제를 해결하였다.

 

LCS의 길이를 구하기 위한 공식

 이 공식을 활용하여 테이블을 그려보았다.

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

 우선 i와 j가 0인 배열에 0을 채워준다. 그 뒤로 C와 A, C와 C, C와 A, C와 Y ... 를 비교하며 테이블 값을 채워나간다.

 

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

 

import java.io.*;

public class Baekjoon9251 {

    private static int[][] dpTable;

    private static void LCS(Character x, int i, Character y, int j) {
        if (i == 0 || j == 0) dpTable[i][j] = 0;
        else if (x == y) {
            dpTable[i][j] = dpTable[i - 1][j - 1] + 1;
        } else if (x != y) {
            dpTable[i][j] = Math.max(dpTable[i][j - 1], dpTable[i - 1][j]);
        }
    }

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String a = "0" + bufferedReader.readLine();
        String b = "0" + bufferedReader.readLine();
        dpTable = new int[a.length()][b.length()];

        for (int i = 0; i < dpTable.length; i++) {
            for (int j = 0; j < dpTable[0].length; j++) {
                LCS(a.charAt(i), i, b.charAt(j), j);
            }
        }

        bufferedWriter.write(String.valueOf(dpTable[a.length() - 1][b.length() - 1]));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}