baekjoon 9251:LCS

baekjoon 9251 LCS

9251번 LCS

접근

대표적인 dp문제인 LCS이다. 앞에서 부터 비교해서 같으면 +1하고 둘다 index+1
다르면 각각 index+1해보고 max찾기

코드

#include <iostream>
#include <string.h>

using namespace std;
string s1, s2;
int dp(int i, int j);
int cache[1000][1000];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  memset(cache, -1, sizeof(cache));
  cin >> s1 >> s2;
  cout << dp(0, 0);

  return 0;
}
int dp(int i, int j) {
  if (i == s1.size() || j == s2.size())
    return 0;
  int &ret = cache[i][j];
  if (ret != -1)
    return ret;
  ret = 0;
  if (s1[i] == s2[j])
    ret = dp(i + 1, j + 1) + 1;
  else
    ret = max(dp(i + 1, j), dp(i, j + 1));
  return ret;
}

배운 점

dp알고리즘 응용해보았다.