[C++] 9251: LCS

🖍️ 겪은 문제

• 한 글자씩 이동시켜가면서.. 누적해서 탐색해야하나? 생각을 했는데 풀이 방법이 떠오르질 않았다.
• 보통 이러면 DP더라.

🔍 해결 방법

• A문자열에 대한 인덱스 i, B문자열에 대한 인덱스 j를 1씩 증가시켜가면서 LCS값을 누적하며 계산해서 최종적으로 [A문자열 길이][B문자열 길이]를 알아낸다. -> DP로 풀이해야 한다.
• DP설계하기 : dp[i][j]를 A문자열의 i번째 문자까지 부분 문자열과, B문자열의 j까지 부분 문자열 간의 LCS 길이라고 하자.
• 점화식 세우기
  • dp[i][j]가 같으면 현재 비교하는 문자 이전 까지 비교한 거에 1더한거 => dp[i][j] = dp[i-1][j-1] + 1
  • 같지 않으면 A에서 하나 빼고 & B 그대로, A 그대로 & B에서 하나 뺀거 중에 더 큰 LCS값 가져오기.  => max(dp[i-1][j], dp[i][j-1]) (현재 비교하는 문자열을 포함해도 괜찮으므로)

📇 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();

    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            if (A[i-1] == B[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] << '\n';
    return 0;
}