[09251] LCS

[09251] LCS

문제

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

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

입력

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

출력

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

코드

#include <iostream>
#include <string>

using namespace std;

/* 조건 */
#define MAX_N 1001

/* 변수 */
string X, Y;
int dp[MAX_N][MAX_N];

/* 함수 */
void init() {
    for(int i = 0; i < MAX_N; i++)
        for(int j = 0; j < MAX_N; j++)
            dp[i][j] = -1;
}

int LCS(int i, int j) {
    if(i < 0 || j < 0) return 0;

    int& ret = dp[i][j];
    if(ret > -1) return ret;

    if(X[i] == Y[j])
        return ret = LCS(i-1, j-1) + 1;
    else return ret = max(LCS(i-1, j), LCS(i, j-1));
}

int main() {
    /* 입력 */
    cin >> X;
    cin >> Y;

    /* 풀이 */
    init();

    cout << LCS(X.length() - 1, Y.length() - 1) << '\n';
}

풀이

변수

• string X, Y 두 문자열 X와 Y
• dp[i][j] X의 i번째 문자와 Y의 j번째 문자열 까지의 LCS 길이를 저장한 배열

함수

• 이번 풀이에서는 풀이과정을 포함한 함수를 설명하면서 개념을 소개하겠다.
• init() 초기 설정을 하는 함수. dp[] 배열을 전부 -1로 초기화 해주었다.
• LCS(i, j) dp[i][j]에 값이 없으면 (-1 이면) 값을 채우고 해당 값을 return한다.
  • dp[i][j]을 구하는 방법은 다음과 같다.
  • X[i]와 Y[j]를 비교한다.
  • 만약 X[i]와 Y[j]가 같다면, LCS(i-1, j-1) + 1 을 return한다.
    • 설계대로라면 LCS(i, j) 함수는 X의 i번째 문자와 Y의 j번째 문자 까지의 LCS를 구한다.
    • 따라서 X[i]와 Y[j]가 같으면 해당 문자들 이전까지의 LCS인 LCS(i-1, j-1)에 1을 더해 return하면 된다.
  • 만약 둘이 같지 않다면, LCS(i-1, j)와 LCS(i, j-1) 중 더 큰 수를 return한다.
    • LCS(i-1, j)와 LCS(i, j-1)의 의미는 각 문자들을 앞으로 옮겨가며 끝까지 탐색하는 것이다.
    • 모든 경우를 탐색하게 되는 것.

출처

백준 [09251] LCS
https://www.acmicpc.net/problem/9251