문제

LCS

LCS2

LCS

두 문자열의 공통 부분중 가장 긴 것의 길이를 찾는 문제이다.
길이만 찾으면 되므로 다른 문제와 다를 바가 없었다.
A의 인덱스와 B의 인덱스를 증가시키며 둘이 일치하면 길이 + 1한다.

수식

문자 일치할 경우

dp[i][j] = dp[i+1][j+1]+1

일치하지 않을 경우

dp[i][j] = max(dp[i+1][j], dp[i][j+1])

코드

// 2022.02.24 17:56:51
// 9251 https://boj.kr/9251
#include <bits/stdc++.h>
using namespace std;

string a, b;
int dp[1001][1001];

int f(int ai, int bi)
{
    if (ai >= a.length() || bi >= b.length())
        return 0;
    int &ret = dp[ai][bi];
    if (ret != -1)
        return ret;

    if (a[ai] == b[bi])
    {
        ret = f(ai + 1, bi + 1) + 1;
    }
    else
    {
        int l = f(ai + 1, bi);
        int r = f(ai, bi + 1);
        ret = max(l, r);
    }

    return ret;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    memset(dp,-1,sizeof(int)*1001*1001);
    cin >> a >> b;
    cout << f(0, 0);
}

LCS 2

LCS + 경로도 찾아야 하는 문제이다.
기본적으로는 기존 문제와 같다.
기존 문제를 풀고, 발생하는 DP 배열을 다시 탐색하여 다시 계산하지 않고 경로를 출력했다.

코드

// 2022.02.26 13:54:58
// 9252 https://boj.kr/9252
#include <bits/stdc++.h>
using namespace std;

string a, b;

int dp[1001][1001];

int f(int ai, int bi)
{
    if (ai >= a.length() || bi >= b.length())
        return 0;

    int &ret = dp[ai][bi];
    if (ret != -1)
        return ret;

    if (a[ai] == b[bi])
    {
        return ret = f(ai + 1, bi + 1) + 1;
    }

    int l = f(ai + 1, bi);
    int r = f(ai, bi + 1);
    return ret = max(l, r);
}

void d(int ai, int bi)
{
    if (ai >= a.length() || bi >= b.length())
        return;

    if (a[ai] == b[bi])
    {
        cout << a[ai];
        d(ai + 1, bi + 1);
        return;
    }

    if (dp[ai + 1][bi] > dp[ai][bi + 1])
    {
        d(ai + 1, bi);
    }
    else
    {
        d(ai, bi + 1);
    }
    return;
}

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

    cin >> a >> b;
    memset(dp, -1, sizeof(int)*1001*1001);
    cout << f(0, 0) << '\n';
    d(0, 0);
}