<DP> BOJ 9251 LCS

문제

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

• 각 문자열의 길이 <= 1000

접근

LCS는 매우 유명하고 접근이 전형적이기 때문에 어떻게 접근하는지에 대한 설명보단 어떻게 해결하는지에 초점을 두고 설명을 하도록 하겠습니다.

• 1. d[i][j]를 문자열 하나의 처음부터 i까지의 substring과 다른 문자열의 처음부터 j까지의 substring에 대한 LCS라고 정의합니다.
• 2. dp로 접근했으면 마지막에 집중해봅니다.
  • 1. i와 j가 LCS의 마지막 문자가 되는 경우
       d[i-1][j-1]+1
  • 2. i와 j가 LCS가 아닌 경우
    • 2-1. i를 안 쓸 경우
      d[i-1][j]
    • 2-2. j를 안 쓸 경우
      d[i][j-1]
• 3. 위의 총 3가지 경우 중 최대값이 d[i][j]가 됩니다.
• 4. 시간 복잡도
     총 배열의 수 * 각 원소를 구하기 위해 참고한 개수 = $O(3N^2)$

LCS를 해결하는 방법은 LCS에만 사용되지만 전형적이므로 외워두는 것이 좋습니다. 아래 이미지는 문자열 CALENDAR와 CABLENDR의 LCS를 구하는 DP를 나타낸 것 입니다. 기저값이 0인 점도 명확하게 볼 수 있습니다.

코드

import java.io.*;
import java.util.*;

class baek__9251 {
    static String s;
    static String ss;
    static int[][] d = new int[1000][1000];

    static int go(int i, int j) {
        if (i < 0 || j < 0)
            return 0;

        if (d[i][j] != -1) {
            return d[i][j];
        }

        int a = go(i - 1, j - 1);
        if (s.charAt(i) == ss.charAt(j))
            a++;

        int b = go(i - 1, j);
        int c = go(i, j - 1);

        d[i][j] = Math.max(a, b);
        d[i][j] = Math.max(d[i][j], c);

        return d[i][j];
    }

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

        s = br.readLine();
        ss = br.readLine();

        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < ss.length(); j++) {
                d[i][j] = -1;
            }
        }

        System.out.print(go(s.length() - 1, ss.length() - 1));
    }
}