[백준 - 9251] LCS - C++

분류: DP /

 

문제

문제 링크

문제 설명

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

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

입력

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

출력

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

 

풀이

#include <iostream>
#include <string>
using namespace std;
int max(int a, int b) {return a > b ? a : b;}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string str1, str2; cin >> str1 >> str2;
    int dp[str1.length()+1][str2.length()+1];
    
    for(int i=0; i<=str1.length(); i++) {
        for(int j=0; j<=str2.length(); j++) {
            if(i == 0 or j == 0) dp[i][j] = 0;
            else if(str1[i-1] == str2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }
    cout << dp[str1.length()][str2.length()];
}

 

`LCS`는 최장 공통 부분 수열(`Longest Common Subsequence`)혹은 최장 공통 문자열(`Longest Common Substring`)을 말한다.

 

`최장 공통 부분 수열`은 [백준 - 11053] 가장 긴 증가하는 부분 수열문제처럼 부분 수열을 찾는 문제이고 `최장 공통 문자열`은 연속되는 문자열을 찾는 문제로 최대 공약수와 비슷하다.

LCS vs LCS

Longest Common Subsequence

`dp[i][j]`는 `str1[:i]`와 `str2[:j]`의 최장 공통 부분 수열을 의미한다.