[백준 9251번 C/C++] LCS (Longest Common Subsequence, 최장 공통 부분 수열)

[백준 9251번 C/C++] LCS 

 

 

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

9251번: LCS

---

 

해결방안

 

다이나믹 프로그래밍 Dynamic Programming, DP

LCS (Longest Common Subsequence, 최장 공통 부분 수열)

 

---

 

정답 코드

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

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

    string a, b;
    cin >> a >> b;

    int aSize = a.size(); // 첫 번째 문자열의 길이
    int bSize = b.size(); // 두 번째 문자열의 길이
    vector<vector<int>> dp(aSize+1, vector<int>(bSize+1, 0));

    for (int i = 1; i <= aSize; i++){ 
        for (int j = 1; j <= bSize; j++) 
        {
            // 두 문자가 같다면, LCS는 대각선 위의 값에서 +1된 값
            if (a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            
            else // 두 문자가 다르다면, LCS는 왼쪽 또는 위쪽 값 중 큰 값                
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }   
    }

    cout << dp[aSize][bSize]; // 가장 긴 공통 부분 수열의 길이 출력

    return 0;
}

 

시간 복잡도가 O(N*M)

---