9251-LCS(Longest Common Subsequence)

www.acmicpc.net/problem/9251

9251번: LCS

본 문제의 제목은 LCS(Longest Common Subsequence)입니다. 이름만 봐도 유명한 문제라는 느낌이 들어 서칭을 바로 해보았습니다. 역시나 유명한 문제였습니다.

 

LCS는 Longest Common Substring과 Longest Common Subsequence이 존재합니다.

2개는 다른 의미를 가지므로 구분해야합니다. 차이점은 공통되는 부분의 연속 여부입니다.

Longest Common Substring

Input1: ABCDHEF

Input2: BCDEF

Output: BCD

 

연속적으로 공통되는 부분을 탐색

Longest Common Subsequence

Input1: ABCDHEF

Input2: BCDEF

Output: BCDEF

 

불연속적으로 공통되는 부분도 탐색

 

본 문제는 Longest Common Subsequence에 관한 문제입니다. 해당 문제 및 알고리즘의 경우 잘 정리된 게시글이 많기에 제가 참고한 게시글의 링크를 첨부합니다.

 

twinw.tistory.com/126

LCS(Longest Common Subsequence) 알고리즘

www.crocus.co.kr/787

LCS(Longest Common Subsequence) 알고리즘

코드

#include <iostream>
#include <string>

using namespace std;

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

int main()
{
    string str1;
    string str2;

    //freopen("9251.txt", "r", stdin);
    cin >> str1 >> str2;

    str1 = '0' + str1;
    str2 = '0' + str2;

    for(int i = 0; i <= 1000; i++) dp[0][i] = 0;
    for(int i = 0; i <= 1000; i++) dp[i][0] = 0;

    for(int idx_str2 = 1; idx_str2 < str2.size(); idx_str2++)
        for(int idx_str1 = 1; idx_str1 < str1.size(); idx_str1++)
        {
            if (str1[idx_str1] == str2[idx_str2])
            {   
                //왜 좌상단에 있는 값을 가져오는 걸까?
                //->새 글자가 추가 되기전에 최대로 가졌던 LCS 값을 가져와야함
                // ABC BC 는 AB, B 의 LCS 값에 + 1
                dp[idx_str1][idx_str2] = dp[idx_str1 - 1][idx_str2 - 1] + 1;
            }
            else
            {
                dp[idx_str1][idx_str2] = max(dp[idx_str1][idx_str2 - 1], dp[idx_str1 - 1][idx_str2]);
            }
        }


    cout << dp[str1.size()-1][str2.size()-1];
    return 0;
}