백준 9251번 LCS

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

9251번: LCS

 

풀이

가장 대표적이고 기본적인 LCS 길이 찾기 문제이다.

LCS 길이 찾기 방법 : https://suhwanc.tistory.com/80

LCS 알고리즘

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
int d[1001][1001];
int main()
{
    string a, b;
    string ak, bk;
    a = " "; b = " ";
    cin >> ak >> bk;
    a += ak; b += bk;
    int na = a.size();
    int nb = b.size();
    for (int i = 1; i < na; i++) {
        for (int j = 1; j < nb; j++) {
            if (a[i] == b[j]) {
                d[i][j] = d[i - 1][j - 1] + 1;
            }
            else {
                d[i][j] = max(d[i - 1][j], d[i][j - 1]);
            }
        }
    }
    printf("%d\n", d[na - 1][nb - 1]);
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~