[C++] 백준 9251 LCS

#include <iostream>
#include <algorithm>
 
int DP[1001][1001] = {};
 
int main() 
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::string s1 = {};
    std::string s2 = {};
    std::cin >> s1 >> s2;
 
    for (int i = 1; i <= s1.size(); ++i)
    {
        for (int j = 1; j <= s2.size(); ++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 - 1][j], DP[i][j - 1]);
            }
        }
    }
 
    std::cout << DP[s1.size()][s2.size()];
    return 0;
}

DP문제입니다.

단순한데 쉽지 않은 문제였습니다...

생각하는 게 어려웠습니다.

1개씩 확인하기 때문에 맞는 경우  차이에서 한개만 올려줍니다. (한 개 차이에서 두개가 맞을 수는 없으니까요)

틀리는 경우에는 한개 차이에서 가장 큰 숫자를 올려줍니다.