[알고리즘 문제 풀기] LCS(9251)

1. 문제 풀이 아이디어

• DP를 이용하여 두 문자열의 LCS(최장 공통 부분 수열) 길이를 구한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    String a = sr.ReadLine();
    String b = sr.ReadLine();
    int[,] dp = new int[a.Length + 1, b.Length + 1];
    for (int i = 1; i <= a.Length; i++)
    {
        for (int j = 1; j <= b.Length; j++)
        {
            if (a[i-1] == b[j-1]) dp[i, j] = dp[i - 1, j - 1] + 1;
            else dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
        }
    }
    sw.WriteLine(dp[a.Length,b.Length]);
}

3. 정리

• dp[i, j]는 a의 i번째 문자와 b의 j번째 문자까지 고려했을 때 LCS의 길이를 저장한다.

• a[i-1] == b[j-1]이면 dp[i-1, j-1] + 1로 갱신하여 공통 부분 수열을 확장한다.

• 다르면 dp[i-1, j]와 dp[i, j-1] 중 최댓값을 선택하여 현재 위치의 최장 길이를 유지한다.