백준 1958번 : LCS 3

  LCS를 한 번이라도 풀어봤다면 어려운 문제는 아니다. 단지 3차원 배열을 사용해야 하기 때문에 시각적으로 표현하기가 어려울 뿐..! 더 자세한 풀이는 아쉽게도 내 블로그에 적어놓은 글 중에는 LCS 관련 풀이가 없어서 그나마 비슷한 공통부분문자열(https://stillchobo.tistory.com/92)을 참고하면 좋을 것 같다.

 

  아래 풀이는 공통부분문자열의 풀이에서 발전된 형태다. 복잡할 것 없이 dp의 값이 증가하는 경우는 단 하나 밖에 없다.

 

  문자가 같을 때! 이때 dp의 값은 1 증가하게 된다. 다시 한 번 말하지만 dp의 값이 변화하는 때는 이 때 뿐이다.

 

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

 

  이제 그 외의 경우(문자가 같지 않을 때)를 처리해주면 된다. 공통부분문자열과는 다르게 분절적이여도 되기 때문에 이전 값들 중 최댓값을 할당해준다.

 

#include <iostream>

using namespace std;

string a, b, c;
int dp[102][102][102];

int strlen(string str)
{
    int len = 0;
    while(str[len]) len += 1;
    return len;
}

int main()
{
    cin >> a >> b >> c;

    int a_len = strlen(a);
    int b_len = strlen(b);
    int c_len = strlen(c);
        
    int ans = 0;
    
    for(int i = 1; i <= a_len; i++)
    {
        for(int j = 1; j <= b_len; j++)
        {
            for(int k = 1; k <= c_len; k++)
            {
                if(a[i-1] == b[j-1] && b[j-1] == c[k-1]) dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                else
                {
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1]);
                }
                ans = max(ans , dp[i][j][k]);
            }
        }
    }
    
    cout << ans;
    
    return 0;
}