LCS 9251

문제

접근 방법

일치하지 않을 경우 DP[i][j]=MAX(DP[i-1][j],DP[i][j-1])이다.
ACAY, CAPCA로 예를 들면 맨 끝부분이 일치하지 않기에 앞부분에 해당하는 (ACA, CAPCA)와 (ACAY, CAPC) 중 긴 길이를 가져가면 된다.
일치할 경우 이전 문자에서 이어지게 하면 된다.

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

표를 그린 뒤 규칙을 찾아낼 수도 있다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    string str1, str2;
    cin >> str1 >> str2;
    vector<vector<int>> dp(str2.size() + 1, vector<int>(str1.size() + 1, 0));
    for (int i = 1; i <= str2.length(); ++i)
        for (int j = 1; j <= str1.length(); ++j)
        {
            if (str1[j - 1] == str2[i - 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[str2.size()][str1.size()];
    return 0;
}

풀이

LCS는 DP를 배울 때 꼭 만나는 문제 중 하나라고 생각한다.
규칙을 찾아내는 법을 배우는 것이 중요하다.