[BOJ] 9251번 LCS c++

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

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

---

입력 1
ACAYKP
CAPCAK

출력 1
4

---

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

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

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

  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;
      else
        dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
    }
  }

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

두 가지 케이스로 나뉜다.
1. 두 문자열의 현재 문자가 일치할 때
2. 두 문자열의 현재 문자가 일치하지 않을 때
1번의 경우에는 두 문자열에서 직전 문자까지 봤을 때 구한 답에 1을 더해주고, 2번의 경우에는 이전에 구한 값 중 큰 값을 넣어준다. 자세한 건 아래 예시를 참고하자.

예를 들어, ABC AABC가 있다.

-	0	A	B	C
0	0	0	0	0
A	0	1	1	1
A	0	1	1	1
B	0	1	2	2
C	0	1	2	3

1번의 경우는 문자열 ABC와 AABC의 3이다. AB와 AAB까지 비교할 때 LCS의 길이는 2이고, 여기에 현재 일치하는 문자 'C'를 더하면 2가 된다.
2번의 경우는 문자열 ABC와 AAB의 2이다. C와 B가 일치하지 않으므로, C와 B를 각각 LCS에 포함해본다. C를 포함한 ABC와 AA의 LCS는 1이고, B를 포함한 AB와 AAB의 LCS의 길이는 2이다. 따라서 ABC와 AAB의 LCS의 길이는 더 큰 값인 2가 된다.

dp를 푸는데 소요되는 시간 중 90%는 아마 아이디어 생각하기가 아닐까 싶다. 다른 사람들이 세운 점화식을 보면 '저걸 어떻게 생각하지' 싶을 정도로 점화식이 참 다양하더라. 그러한 아이디어가 내 머릿속에서 나오면 얼마나 좋겠느냐마는, 그전까지 몰라서 찾아보는 것도 좋은 공부법이라 생각한다. 보고, 익히고, 시간이 흐른 뒤에 스스로 힘으로 풀어보자. dp 척척박사 되는 길은 많은 문제, 다양한 문제를 접하고 시야를 넓히는 길이다. 💪🏻