백준 9251 - LCS (C++)

qqlzzb 2022. 9. 13. 23:43

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

9251번: LCS

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

www.acmicpc.net

풀이

LCS는 최장 공통 부분 수열로 dp로 구현할 수 있다.

관련 포스팅은 --> https://qqs-diary.tistory.com/132

코드

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

int dp[1001][1001];
char s1[1001],s2[1001];
int main()
{
    scanf("%s %s",s1+1,s2+1);
    int i=1,j=1;
    for(i=1; s1[i]; i++)
    {
        for(j=1; s2[j]; j++)
        {
            dp[i][j]=max({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]+(s1[i]==s2[j])});
        }
    }
    cout<<dp[i-1][j-1];
}