백준 9251 "LCS (최장 공통 부분 수열)" (JAVA)

🔍 문제링크

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

---

📌 문제 요약

• 두 문자열 str1과 str2가 주어졌을 때, 최장 공통 부분 수열(LCS: Longest Common Subsequence)의 길이를 구하는 문제.
• LCS는 연속되지 않아도 됨 -> 순서만 유지하면 됨.
  • ACAYKP, CAPCAK에서는 `ACAK`가 LCS

---

🛠 풀이 및 알고리즘

1. dp[i][j] 정의
   • dp[i][j]: `str1[0:i]`와 `str2[0:j]`의 LCS 길이.
2. 점화식 (DP)
   • 문자가 같으면 `dp[i][j] = dp[i-1][j-1] + 1`
     -> 두 문자가 같다면 이전 LCS 길이에 1증가.
   • 문자가 다르면 `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`
     -> 이전 문자열 중 더 긴 LCS를 유지.
3. 결과 출력
   • dp[n][m]을 출력 (`n = str1.length(), m = str2.length()`).

---

💡 코드

public class Baekjoon_9251 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str1 = sc.next();
        String str2 = sc.next();

        int n = str1.length();
        int m = str2.length();

        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

---

🏆 시간 복잡도 분석

• O(NM)
•  N ≤ 1000, M ≤ 1000 → 최악의 경우 1,000,000