๐๏ธ ๊ฒช์ ๋ฌธ์
- ํ ๊ธ์์ฉ ์ด๋์์ผ๊ฐ๋ฉด์.. ๋์ ํด์ ํ์ํด์ผํ๋? ์๊ฐ์ ํ๋๋ฐ ํ์ด ๋ฐฉ๋ฒ์ด ๋ ์ค๋ฅด์ง ์์๋ค.
- ๋ณดํต ์ด๋ฌ๋ฉด DP๋๋ผ.
๐ ํด๊ฒฐ ๋ฐฉ๋ฒ
- A๋ฌธ์์ด์ ๋ํ ์ธ๋ฑ์ค i, B๋ฌธ์์ด์ ๋ํ ์ธ๋ฑ์ค j๋ฅผ 1์ฉ ์ฆ๊ฐ์์ผ๊ฐ๋ฉด์ LCS๊ฐ์ ๋์ ํ๋ฉฐ ๊ณ์ฐํด์ ์ต์ข
์ ์ผ๋ก [A๋ฌธ์์ด ๊ธธ์ด][B๋ฌธ์์ด ๊ธธ์ด]๋ฅผ ์์๋ธ๋ค. -> DP๋ก ํ์ดํด์ผ ํ๋ค.
- DP์ค๊ณํ๊ธฐ : dp[i][j]๋ฅผ A๋ฌธ์์ด์ i๋ฒ์งธ ๋ฌธ์๊น์ง ๋ถ๋ถ ๋ฌธ์์ด๊ณผ, B๋ฌธ์์ด์ j๊น์ง ๋ถ๋ถ ๋ฌธ์์ด ๊ฐ์ LCS ๊ธธ์ด๋ผ๊ณ ํ์.
- ์ ํ์ ์ธ์ฐ๊ธฐ
- dp[i][j]๊ฐ ๊ฐ์ผ๋ฉด ํ์ฌ ๋น๊ตํ๋ ๋ฌธ์ ์ด์ ๊น์ง ๋น๊ตํ ๊ฑฐ์ 1๋ํ๊ฑฐ => dp[i][j] = dp[i-1][j-1] + 1
- ๊ฐ์ง ์์ผ๋ฉด A์์ ํ๋ ๋นผ๊ณ & B ๊ทธ๋๋ก, A ๊ทธ๋๋ก & B์์ ํ๋ ๋บ๊ฑฐ ์ค์ ๋ ํฐ LCS๊ฐ ๊ฐ์ ธ์ค๊ธฐ. => max(dp[i-1][j], dp[i][j-1]) (ํ์ฌ ๋น๊ตํ๋ ๋ฌธ์์ด์ ํฌํจํด๋ ๊ด์ฐฎ์ผ๋ฏ๋ก)
๐ ์ฝ๋
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
string A, B;
cin >> A >> B;
int n = A.size(), m = B.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
if (A[i-1] == B[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] << '\n';
return 0;
}