[BOJ/JAVA] P9251 LCS

---

문제 설명

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

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

---

INPUT & OUTPUT

INPUT

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

예제 입력 1

ACAYKP
CAPCAK

OUTPUT

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

예제 출력 1

4

---

STRATEGY

1. 각 부분수열끼리 비교한다.
2. 각 부분수열에 원소 하나 추가될 때를 비교한다.
   1) 추가된 원소가 같다면 이전 LCS에서 +1 해준다.
   2) 추가된 원소가 다르다면 이전 부분수열의 LCS 중 큰걸 고른다.

👉 부분수열에서 순서가 지켜지기 때문에 각 문자열들의 문자들을 서로 비교하면서 서로 같으면 값을 1씩 증가시키면서 누적합을 구하는 것이다.

---

SOLUTION

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

public class Main {

    private static Integer[][] dp;
    private static char[] arr1;
    private static char[] arr2;

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

        arr1 = br.readLine().toCharArray();
        arr2 = br.readLine().toCharArray();
        dp = new Integer[arr1.length][arr2.length];

        System.out.println(LCS(arr1.length - 1, arr2.length - 1));
    }

    private static int LCS(int x, int y) {
        if (x == -1 || y == -1) {
            return 0;
        }

        if (dp[x][y] == null) {
            dp[x][y] = 0;

            if (arr1[x] == arr2[y]) {
                dp[x][y] = LCS(x - 1, y - 1) + 1;
            } else {
                dp[x][y] = Math.max(LCS(x - 1, y), LCS(x, y - 1));
            }
        }

        return dp[x][y];
    }
}

---

REMIND

놓쳤던 부분

• 이전에 풀었던 전깃줄과 비슷하다고 생각했다.
• 한 배열을 기준으로 다른 배열에서 순서대로 한 글자씩 가져와 비교했다.
  • charAt() 과 contains()를 곁들인...
• 중복된 글자가 있는 경우, charAt()으로 원하는 글자의 index를 파악하는 데 실패했다. 이로 인해 순서를 비교할 수 없었다.
• 그리고 이전까지의 문제와 똑같이 부분 수열의 시작점을 달리해야 할거라 생각했는데, 전혀 그럴 필요가 없었다. 위에서 언급했듯이 순서가 고정이기 때문이다. → 이전에 무얼 선택하느냐에 따라 이후에 달라지는 게 없다는 말이다.

reference

• https://st-lab.tistory.com/139