[C++] 9251. LCS

대표적인 dp문제이다.

하지만, 나는.. 바보같이 처음에 map써봤다가 당차게 틀려먹었다.. (대체 왜이러니..)

map쓰면 문자열을 계속 순회해야해서 시간복잡도에서 걸린다. 그리고 이건 대표적인 dp라서 그냥 내가 바보였던것으로.. 넘어갑시다.

 

아무튼, dp를 이용해서 각 부분 문자열에 대한 LCS 값을 구해나가면 된다!

여기서 dp의 경우의 수는 두가지인데,

1. i번째 문자열 == j번째 문자열
   이건 왼쪽 위 대각선 값에 +1 해주면된다. 왼쪽 위 대각선 값이 이전 문자열인 (i-1,j-1)의 LCS 값이기 때문!
2. i번째 문자열 != j번째 문자열
   이건 왼쪽과 위 중 max값을 가져가면 된다.

 

 

 

<코드>

#include <iostream>
#include <string>
using namespace std;

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

    string one, two;
    cin >> one >> two;
    int n = one.size();
    int m = two.size();

    int dp[1001][1001] = {0};
    //빈문자열과의 LCS처리를 위해 1부터 시작
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(one[i-1]==two[j-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[n][m];
    
    return 0;
}