[백준 9251번] LCS(C++)

dp문제가 왜이렇게 많아....

아이디어

각 string(A,B)에 맞는 dp배열을 생성하고

각 (i,j)칸은 A[i-1] , B[j-1] 까지의 string을 비교한 것이다.

ex) dp[3][4] = ACA * CAPC 비교해서 만들어진 칸.

아 설명 못하겠당..

C++풀이

#include <bits/stdc++.h>

using namespace std;
string A,B;
int dp[1001][1001];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> A >> B;
    int result = INT_MIN;
    for(int i = 1 ; i<=A.length(); i++)
    {
        for(int j = 1 ; j<= B.length(); j++)
        {
        	//비교해서 같다면, 왼쪽 위의 값 +1
            if(A[i-1] == B[j-1]) dp[i][j] =dp[i-1][j-1] + 1;
            //다르다면 max(위, 좌) 값을 가져옴
            else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            
            //dp 최대값 찾기
            if(dp[i][j] > result) result = dp[i][j];
        }
    }
    cout << result;
}