[백준] 1958_LCS 3 C++

24 Jul 2023 in Study on Coding Test

DP를 활용해보는 3차원 LCS 문제

정답제출코드

#include <iostream>
#include <string>

#define MAX 101

using namespace std;

int DP[MAX][MAX][MAX];

int m_max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

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

    string s1, s2, s3;
    cin >> s1;
    cin >> s2;
    cin >> s3;

    s1 = ' ' + s1;
    s2 = ' ' + s2;
    s3 = ' ' + s3;

    int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();

    for (int i = 1; i < len1; ++i)
    {
        for (int j = 1; j < len2; ++j)
        {
            for (int k = 1; k < len3; ++k)
            {
                if (s1[i] == s2[j] && s2[j] == s3[k] && s1[i] == s3[k])
                    DP[i][j][k] = DP[i-1][j-1][k-1] + 1;
                else
                    DP[i][j][k] = m_max(DP[i-1][j][k], m_max(DP[i][j-1][k], DP[i][j][k-1]));
            }
        }
    }

    cout << DP[len1-1][len2-1][len3-1];

    return 0;
}

기존 LCS 문제는 2중 포문을 이용해서 구하면 되었다.

그리고 이번 문제는 시간도 2초로 넉넉하고,

최대 문자열의 길이도 100이므로 3중 포문을 이용하는 방법을 채택했다.

두 개의 LCS를 구하는 알고리즘에다가 차원 하나를 더 붙여서 구현하였다.

한 글자 한 글자 비교하면서 문자가 같으면 숫자를 추가해주는 식으로 구현!