[백준 c++] 9251 LCS

문제

https://www.acmicpc.net/problem/9251
두 문자열의 LCS의 길이를 구하는 문제다.

---

풀이

LCS 란?

LCS(Longest Common Subsequence)는 최장 공통 부분 문자열이다.
Subsequence는 Substring과 다르게 연속되지 않은 수열이다.
다만 수열이기 때문에 순서는 따라야한다.
ACBK 와 TBCK 가 있을 때 LCS는 BK 다.

---

LCS와 DP

LCS는 DP로 구할 수 있다.

1. 두 문자열을 char 배열로 저장한다.
2. 이중 for문으로 문자를 하나하나 비교한다.
3. 문자가 일치하면 왼쪽 위의 값 +1을 저장한다.
4. 일치하지 않으면 왼쪽 값, 위쪽 값 중 큰 값을 저장한다.

이렇게 왼쪽, 위쪽을 참고해야하기 때문에 편의상 배열에서 1열과 1행은 0으로 깔아준다.

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
char s1[1001], s2[1001];
int dp[1001][1001], i, j;
int main()
{
    scanf("%s %s", s1 + 1, s2 + 1);
    for (i = 1; s1[i]; i++)
    {
        for (j = 1; s2[j]; j++)
        {
            dp[i][j] = max({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + (s1[i] == s2[j])});
        }
    }
    cout << dp[i - 1][j - 1] << "\n";
}