[Algorithm]Baekjoon 9251번 :: LCS

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

9251번: LCS

int dp[1001][1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    string a, b;
 
    cin >> a >> b;
 
    for (int i = 1; i <= a.size(); i++)
    {
        for (int j = 1; j <= b.size(); j++)
        {
            if (a[i - 1] == b[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
 
    cout << dp[a.size()][b.size()];
}
 

 

코드를 보면 알겠지만 이 문제도 DP로 푸는 문제이다.

일일이 비교하면 당연히 시간초과가 난다.

일단 기본적인 설명은 아래 글이 잘 되어있으니 한번 보는걸 추천.

표로도 예시를 들어놔서 이해하기가 편하다.

 

https://ongveloper.tistory.com/36

백준 9251 LCS c++

 

두 문자가 같을 때 테이블의 왼쪽 대각선에서 +1을 하는 이유는, 해당 문자를 포함하지않은 상태에서의 DP값에서 +1을 해줘야하기 때문이다. 해당 문자를 포함하지 않은 상태에서의 DP값이 바로 왼쪽대각선의 값이다.

 

 

문자가 다를 때 왼쪽이나 위쪽에서 큰 값을 가져오는 이유는, 현재의 문자를 비교하는 과정에서의 바로 이전과정이

DP[i-1][j]와 DP[i][j-1]이기 때문이다. (테이블에서 위와 아래)

이 문제에서의 LCS는 최장 공통 '수열'로 , 공통된부분이 반드시 연속될 필요가 없다.

그렇기 때문에 이전값들을 계속 유지하는게 가능하기 때문에 그냥 제일 큰값을 가져오는게 가능해진다.

 

사실 이거는 그냥 직접 테이블을 보는게 이해가 제일 빠르다...