[백준] 9251_LCS C++

14 Jun 2023 in Study on Coding Test

DP를 이용해서 LCS의 길이를 구해보는 문제

정답제출코드

#include <iostream>
#include <string>

#define MAX 1001

using namespace std;

int dp[MAX][MAX];

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

int main()
{
    string a, b;
    cin >> a;
    cin >> b;

    int aLen = a.length();
    int bLen = b.length();

    for (int i = 1; i < aLen+1; ++i)
    {
        for (int j = 1; j < bLen+1; ++j)
        {
            if (a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = m_max(dp[i-1][j], dp[i][j-1]);   
        }
    }

    cout << dp[aLen][bLen];

    return 0;
}

SSAFY를 준비할 때 문제집에서 DP를 이용해서 LCS를 구하는 문제를 손으로 풀었었다.

그 문제를 그대로 코드로 구현하는 문제였다.

하지만, 표를 이용해서 그렇게 구하는 부분이 이해가 안갔었다.

참고링크를 참고해보니

여기서 LCS는 순서도 같으면서 같은 문자가 몇개냐를 찾는 것이었다.

투 포인터로 풀어도 되지 않을까 생각했지만 다른 문제였던 것 같다.