[LCS] 백준 9251 :: LCS

LCS 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	13835	5899	4352	42.097%

문제

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

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

입력

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

출력

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

예제 입력 1 

ACAYKP
CAPCAK

예제 출력 1 

4

     

 문제 풀이

1차 풀이 (  5896 KB,  8 ms)

Top-Down 방식의 LCS 알고리즘 활용.

두 단어 중 하나의 위치를 증가시키면서 LCS의 길이를 늘려간다.

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1000;
int cache[SIZE][SIZE];
char A[SIZE];
char B[SIZE];

int LCS(int i, int j){
        //! base condition.
        if(i==-1 || j==-1) return 0;

        //! memoization.
        if(cache[i][j] != -1) return cache[i][j];

        //! solving.
        if(A[i] == B[j]) cache[i][j] = LCS(i-1, j-1) + 1;
        else cache[i][j] = max(LCS(i-1, j), LCS(i, j-1));
        return cache[i][j];
}


int main()
{
        cin.tie(nullptr);
        ios::sync_with_stdio(false);

        memset(cache, -1, sizeof cache);
        cin >> A;
        cin >> B;
        
        cout << LCS(strlen(A)-1, strlen(B)-1);
}

2차 풀이 (  5900 KB,  4 ms)

Bottom-UP 방식의 LCS 알고리즘 활용.

#include <bits/stdc++.h>
using namespace std;

string a, b;
int dp[1001][1001];
int main()
{
        memset(dp, 0, sizeof dp);

        cin >> a >> b;
        for (auto i = 1; i <= a.size(); i++){
                for (auto j = 1; j <= b.size(); j++){
                        if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
        }
        cout << dp[a.size()][b.size()];
}