[DP] 9251번 LCS

9251번 LCS

 

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

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

ACAYKP
CAPCAK

 

예제 출력

4

 

해결방법

LCS(Longest Common Subsequence) 를 적용한 DP 문제이다

 

 

⭐️ 솔루션 ⭐️

Longest Common Subsequence 는 common subsequence 중에서 길이가 가장 긴 것을 뜻한다

예를 들어, ABCBDAB , BDCABA 두 문자열의 LCS 는 BCBA 가 된다

 

• 2개의 문자열의 요소를 각각 비교해야하므로 2차원 배열을 준비한다

• 또한 각 비교시, 두 문자열의 요소가 일치하는 경우와 일치하지 않는 경우의 점화식을 다르게 세워 모든 요소를 비교한다
• 점화식은 아래와 같다

L[i,j] = { 0							(i=0 or j=0)
         { L[i-1][j-1] + 1				(xᵢ = yᵢ)
         { max(L[i-1][j], L[i][j-1])	(xᵢ != yᵢ)

 

 

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

string s1,s2;
int d[1001][1001];

void dp(){
    for(int i=1; i<=s1.size(); i++){
        for(int j=1; j<=s2.size(); j++){
            if(s1[i-1] == s2[j-1]){
                d[i][j] = d[i-1][j-1] + 1;
            }else{
                d[i][j] = max(d[i-1][j],d[i][j-1]);
            }
        }
    }
    
    cout << d[s1.size()][s2.size()] << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> s1 >> s2;
    
    dp();
    
    return 0;
}