[백준] 9251번 - LCS [Java][C++]

문제 링크

---

1. 문제 풀이

전형적인 LCS 알고리즘 문제로 2차원 dp 테이블을 활용해서 구현했다.

문자열 $A$, $B$ 의 LCS를 구하는 dp 점화식은 아래와 같다.

\[dp[i][j] = \begin{cases} 0, & \text{if } i = 0 \text{ or } j = 0 \\\\ dp[i-1][j-1] + 1, & \text{if } A[i] = B[j] \\\\ \max(dp[i-1][j],\ dp[i][j-1]), & \text{otherwise} \end{cases}\]

---

2. 코드

1. Bottom-Up dp [Java]

dp 테이블 앞에 패딩을 한 칸씩 줬다.

import java.io.*;

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

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int N = str1.length;
        int M = str2.length;

        int[][] dp = new int[1 + N][1 + M];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (str1[i - 1] == str2[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]);
    }
}

2. Bottom-Up dp [C++]

dp 테이블 앞에 패딩을 한 칸씩 줬다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;

    int n = s1.size();
    int m = s2.size();

    vector<vector<int>> dp(1 + n, vector<int>(1 + m));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m];
}

---

3. 풀이 정보

1. Bottom-Up dp [Java]

언어	시간	메모리	코드 길이
Java 11	124 ms	18268 KB	759 B

2. Bottom-Up dp [C++]

언어	시간	메모리	코드 길이
C++ 17	4 ms	6004 KB	560 B

---