[BOJ] LCS - 9251

🎨 문제

9251번: LCS

📘 풀이

이 문제는 DP로 풀 수 있습니다. 우선 LCS(Longest Common Subsequence)를 예시로 이해해봅시다. 

 

우선 두 문자열이 주어집니다. (더 많을 수도 있지만 문제에서는 2개가 주어집니다.)

• ACAYKP
• CAPCAK

서브 시퀀스는 주어진 문자열에서 순서를 바꾸지 않고 몇 개의 글자를 뺀 것을 말합니다. 첫 번째 문자열의 경우 ACA, AKP, C 등이 서브 시퀀스가 됩니다. 

 

LCS는 구할 수 있는 모든 서브 시퀀스 중 서로 같은 가장 긴 서브 시퀀스를 의미합니다. 예시의 경우 ACAK가 LCS가 됩니다.

 

LCS를 구하기 위해 모든 서브 시퀀스를 구하고 비교한다면 한 문자열의 서브 시퀀스를 구하는데 오랜 시간이 걸립니다. 하지만 DP를 사용하면 두 문자열의 길이의 곱의 시간으로 LCS를 구할 수 있습니다.

 

길이가 A, B인 문자열이 있을 때 이 두 문자열의 LCS의 길이를 LCS(A, B)라 합시다. 이때 LCS(A, B)는 다음을 만족합니다.

• str1[A] == str2[B] 라면 str1[A]로 끝나는 LCS가 존재한다. 즉, LCS(A, B) = LCS(A -1, B - 1) + 1 을 만족합니다.
• 만약 그렇지 않다면, LCS(A, B) = max(LCS(A - 1, B), LCS(A, B - 1))이 됩니다.

여기에 메모리제이션을 적용해줍니다.

private static int LCS(int x, int y) {

    if (x < 0 || y < 0) return 0;

    if (DP[x][y] != -1) return DP[x][y];

    if (str1[x] == str2[y]) {
        return DP[x][y] = LCS(x - 1, y - 1) + 1;
    }

    return DP[x][y] = Math.max(LCS(x - 1, y), LCS(x, y -1));
}

📗 코드

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

import static java.lang.System.in;

public class Main {

    static int[][] DP;
    static char[] str1, str2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        str1 = br.readLine().toCharArray();
        str2 = br.readLine().toCharArray();
        DP = new int[1004][1004];
        for (int i = 0; i < 1004; i++) {
            Arrays.fill(DP[i], -1);
        }
        System.out.println(LCS(str1.length - 1, str2.length - 1));
    }

    private static int LCS(int x, int y) {

        if (x < 0 || y < 0) return 0;

        if (DP[x][y] != -1) return DP[x][y];

        if (str1[x] == str2[y]) {
            return DP[x][y] = LCS(x - 1, y - 1) + 1;
        }

        return DP[x][y] = Math.max(LCS(x - 1, y), LCS(x, y -1));
    }
}