[BOJ][C#] 9251 LCS

LimJaeJun·2024년 1월 11일

algorithm boj

PS/BOJ

목록 보기

96/108

📕 문제

📌 링크

📗 접근 방식

dp 배열 구성:

dp[i, j]는 첫 번째 문자열 s1의 처음 i개 문자와 두 번째 문자열 s2의 처음 j개 문자에 대한 LCS의 길이를 나타낸다.

초기화:

dp[0, 0]부터 dp[s1Len, s2Len]까지를 채우기 위해 초기화를 진행
dp[0, j]와 dp[i, 0]는 0으로 초기화합 (둘 중 하나의 문자열이 비어있을 때 LCS의 길이는 0)
dp[i, j]는 s1[i-1]과 s2[j-1]이 같을 경우, dp[i-1, j-1] + 1로 갱신
s1[i-1]과 s2[j-1]이 다를 경우, dp[i, j]는 dp[i-1, j]와 dp[i, j-1] 중에서 큰 값으로 갱신

결과 출력

계산된 dp[s1Len, s2Len] 값을 출력

📘 코드

namespace BOJ
{
    class No_9251
    {
        static void Main()
        {
            string s1 = Input(); 
            string s2 = Input();

            int answer = GetLCS(s1, s2);
            
            Console.WriteLine(answer);
        }

        static int GetLCS(string s1, string s2)
        {
            int s1Len = s1.Length;
            int s2Len = s2.Length;

            // dp[i, j] => s1을 i까지 s2를 j까지 사용했을 때의 최소공통부분조합
            int[,] dp = new int[s1Len + 1, s2Len + 1];
            
            // dp 세팅
            // 둘 중 한개라도 0개의 길이를 사용한다면 무조건 0
            dp[0, 0] = 0;
            dp[0, 1] = 0;
            dp[1, 0] = 0;

            for (int i = 1; i <= s1Len; i++)
            {
                for (int j = 1; j <= s2Len; j++)
                {
                    if (s1[i - 1] == s2[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]);
                    }
                }
            }

            return dp[s1Len, s2Len];
        }

        static string Input() => Console.ReadLine();
    }
}