[Algorithm]Baekjoon 9252번 :: LCS 2

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

9252번: LCS 2

 
int dp[1001][1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string s1, s2;
    int maxLength = 0;
 
    cin >> s1 >> s2;
 
    for (int i = 1; i <= s1.size(); ++i)
    {
        for (int j = 1; j <= s2.size(); ++j)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
            maxLength = max(maxLength, dp[i][j]);
        }
    }
 
    string result = "";
    int y = s1.size();
    int x = s2.size();
 
    while (result.size() != maxLength)
    {
        if (dp[y - 1][x] == dp[y][x])
        {
            y -= 1;
            continue;
        }
        else if (dp[y][x - 1] == dp[y][x])
        {
            x -= 1;
            continue;
        }
        
        y -= 1;
        x -= 1;
        result.push_back(s1[y]);
    }
 
    reverse(result.begin(), result.end());
 
    cout << maxLength << endl;
 
    if (result.size() == 0) return 0;
    cout << result;
}
 
 
 
 

 

어제 LCS 공부좀해서 관련문제 하나 풀어볼까 했는데 마침 solved.ac에서 dp관련 문제푸는 와중에 연습용문제 하나가 껴있었다.

최장공통부분수열의 길이'만' 구하는거면 위 코드의 29번째줄까지만 수행하면 된다.

문자열까지 구해야하는 문제면, 29번째 줄까지를 통해 DP테이블을 업데이트 후,

dp[n][m], 즉 dp[s1.size()][s2.size()] 부터 시작해서 일련의 로직을 수행하면 된다.

 

설명은 

https://maxlevel-trace.tistory.com/608

LCS