알고리즘/BOJ

백준 9251번 LCS

꾸준함. 2018. 2. 6. 23:33

문제 링크입니다: https://www.acmicpc.net/problem/9251

algospot에서 LIS 문제를 풀어본 적이 있기 때문에 비교적 쉽게 접근할 수 있었던 것 같습니다.


/*

LCS(Longest Common Subsequence, 최장 공통 부분 순열) 문제는

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장

긴 것을 찾는 문제이다.

LCS의 길이를 구하시오

*/

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

int cache[1000][1000]; //최대 길이 1000

string s1, s2;

 

int LCS(int idx1, int idx2) //s1 s2의 인덱스를 전달받음

{

        //기저 사례: 문자열의 범위 벗어날 경우

        if (idx1 ==s1.size() || idx2== s2.size())

               return 0;

        int &result = cache[idx1][idx2];

        if (result != -1)

               return result;

        // 3가지의 경우의 수를 고려

        //1. s1만 인덱스 증가했을 경우

        //2. s2만 인덱스 증가했을 경우

        //3. s1 s2 모두 인덱스 증가했을 경우

        return result = max(LCS(idx1 + 1, idx2), max(LCS(idx1, idx2 + 1), LCS(idx1+1, idx2+1)+(s1[idx1]==s2[idx2])));

}

 

int main(void)

{

        cin >> s1 >> s2;

        memset(cache, -1, sizeof(cache));

        cout << LCS(0, 0) << endl;

        return 0;

}


개발환경:Visual Studio 2017


지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

백준 2965번 캥거루 세마리  (0) 2018.02.07
백준 11066번 파일 합치기  (3) 2018.02.07
백준 1520번 내리막 길  (0) 2018.02.05
백준 2156번 포도주 시식  (0) 2018.02.05
백준 2293번 동전 1  (2) 2018.02.05