[알고리즘/백준] 9251: LCS

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

 

1. 문제 접근

LCS는 대표적인 DP 문제로,

두 문자열이 주어졌을 때, 공통으로 나타나는 부분 수열 중 가장 긴 길이를 구하는 문제이다.

 

 

dp[i][j] = 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지 봤을 때 LCS의 길이

 

예제를 보며 DP에서 가장 중요한 점화식을 세워보자.

dp	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

 

1. a[i-1] 과 b[j-1] 의 문자가 같을 때, 공통 수열에 포함시킨다.

 

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

 

 

2. a[i-1] 과 b[j-1] 의 문자가 다를 때, 둘 중 하나를 버린다. 

- A에서 현재 문자를 버릴 경우: dp[i-1][j]

- B에서 현재 문자를 버릴 경우: dp[i][j-1]

이때, 더 긴 수열을 선택한다.

 

 

 

-->  dp[i][j] = std::max(dp[i-1][j], dp[i][j-1])

위 점화식을 통해 코드를 작성할 수 있다.

2. 코드

#include <iostream>
#include <vector>
#include <string>

int lcsLength(std::string s1, std::string s2)
{
    const int length1 = s1.size();
    const int length2 = s2.size();
    std::vector<std::vector<int>> dp(length1 + 1, std::vector<int>(length2 + 1, 0));

    for (int i = 1; i <= length1; ++i)
    {
        for (int j = 1; j <= length2; ++j)
        {
            if (s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = std::max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return dp[length1][length2];
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    std::string s1, s2;

    std::cin >> s1 >> s2;
    std::cout << lcsLength(s1, s2);
}