[BOJ] 9251 - LCS

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

BOJ - LCS

문제 유형: 문자열 처리, 재귀, 다이나믹 프로그래밍

문제 난이도: Gold V

시간 제한: 0.1초

메모리 제한: 256MB

 

문제

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

풀이

dp[i1][i2]는 첫 번째 문자열의 i1인덱스부터의 부분문자열과 두 번째 문자열의 i2인덱스부터의 부분문자열의 LCS를 말한다.

만약 재귀 호출에서 인덱스를 벗어났다면 0을 반환하고, dp값이 있다면 그 dp값을 반환해주는 base case처리를 해준다.

만약 s1[i1] == s2[i2]이면, 공통부분을 찾았다. 즉, 두 문자의 인덱스 모두 1을 더해서 호출하고, 그 값을 dp에 저장한다.

그렇지 않다면, 둘 중 하나씩만 인덱스 1을 올린걸 서로 비교해서 더 큰 값을 dp에 저장하고 반환한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, m;
string s1, s2;

int dp[1001][1001];

int solve(int i1, int i2) {
  if (i1 >= n || i2 >= m)
    return 0;
  if (dp[i1][i2] != -1)
    return dp[i1][i2];

  int res = 0;

  if (s1[i1] == s2[i2])
    return dp[i1][i2] = solve(i1 + 1, i2 + 1) + 1;

  return dp[i1][i2] = max(solve(i1 + 1, i2), solve(i1, i2 + 1));
}

int main(int argc, char *argv[]) {
  cin >> s1 >> s2;
  n = s1.size();
  m = s2.size();
  memset(dp, -1, sizeof(dp));

  cout << solve(0, 0) << "\n";

  return 0;
}