백준 5582번 공통 부분 문자열

🔒문제 url

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

🔑알고리즘

$dp[i][j]$ 를 선언해 각 문자열의 $i$번째 글자와 $j$번째 글자가 같다면, $dp[i][j] = dp[i-1][j-1] + 1$이 성립한다.

$dp$ 배열의 원소 중 최대값이 답이 된다.

🐾부분 코드

for (int i = 0; i < a.length(); i++)
{
    for (int j = 0; j < b.length(); j++)
    {
        if (a[i] == b[j]) dp[i][j] = 1;
        else continue;

		#out of index
        if (!i || !j) continue;

        dp[i][j] += dp[i - 1][j - 1];
        ans = max(ans, dp[i][j]);
    }
}

<$dp$ 배열 갱신>
out of index에 유의하여 점화식을 이용해 배열을 채운다.
두 문자열의 현재 위치에 존재하는 값이 같아야함에 주의하자.

🪄전체 코드

#include <bits/stdc++.h>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

string a, b;
int dp[4001][4001];
int ans = 0;

void INPUT()
{
    IAMFAST
    cin >> a >> b;
}

void solution()
{
    for (int i = 0; i < a.length(); i++)
    {
        for (int j = 0; j < b.length(); j++)
        {
            if (a[i] == b[j]) dp[i][j] = 1;
            else continue;

            if (!i || !j) continue;

            dp[i][j] += dp[i - 1][j - 1];
            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans;
}


int main()
{
    INPUT();
    solution();
}

🥇문제 후기

학교 생활에 치이다가 이번 주말 코테를 앞두고 발등에 용암이 쏟아져 오늘 10문제를 풀었는데, 골드 하위 이하였음에도 반나절이 갈려나갔다. 상당히 불안하지만 할 수 있는만큼 끌어올리리이다..