[BOJ] 9252번 LCS 2 c++

https://www.acmicpc.net/problem/9252

문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

---

입력 1
ACAYKP
CAPCAK

출력 1
4
ACAK

---

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

int dp[1001][1001] = {0,};
string str[1001][1001];

int main() {
  char str1[1001], str2[1001];
  int len1, len2;
  scanf("%s", str1);
  scanf("%s", str2);

  len1 = strlen(str1);
  len2 = strlen(str2);

  for(int i = 0; i <= len1; i++)
    str[i][0] = "";
  for(int i = 0; i <= len2; i++)
    str[0][i] = "";

  for(int i = 0; i < len1; i++) {
    for(int j = 0; j < len2; j++) {
      if(str1[i] == str2[j]) {
        dp[i + 1][j + 1] = dp[i][j] + 1;
        str[i + 1][j + 1] = str[i][j] + str1[i];
      }
      else {
        if(dp[i + 1][j] < dp[i][j + 1]) {
          dp[i + 1][j + 1] = dp[i][j + 1];
          str[i + 1][j + 1] = str[i][j + 1];
        }
        else {
          dp[i + 1][j + 1] = dp[i + 1][j];
          str[i + 1][j + 1] = str[i + 1][j];
        }
      }
    }
  }

  printf("%d\n", dp[len1][len2]);
  cout << str[len1][len2] << endl;
}

LCS도 dp로 풀어버리니 결과가 이렇게 떴다. 메모리를 줄이고자 아래에 백트래킹 기법으로 문자열 뒤부터 하나씩 찾아가는 방법으로 풀었다.

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  char str1[1001], str2[1001];
  int dp[1001][1001] = {0,};
  int len1, len2;
  int i, j;
  string ans = "";

  scanf("%s", str1);
  scanf("%s", str2);

  len1 = strlen(str1);
  len2 = strlen(str2);

  for(i = 0; i < len1; i++) {
    for(j = 0; j < len2; j++) {
      if(str1[i] == str2[j])
        dp[i + 1][j + 1] = dp[i][j] + 1;
      else
        dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
    }
  }

  i = len1 - 1;
  j = len2 - 1;

  while(i >= 0 && j >= 0) {
    if(dp[i + 1][j + 1] == dp[i][j + 1])
      i--;
    else if(dp[i + 1][j + 1] == dp[i + 1][j])
      j--;
    else {
      ans += str1[i];
      i--;
      j--;
    }
  }

  printf("%d\n", dp[len1][len2]);
  for(i = (int)ans.size() - 1; i >= 0; i--)
    printf("%c", ans[i]);
}