[9251번] LCS

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LCS :: http://www.crocus.co.kr/787

LCS의 개념 및 이번 문제에 대한 풀이는 위의 LCS 링크에 있습니다.

ACAYKP
CAPCAK

에서 정답은

ACAYKP
CAPCAK

다음과 같이 굵은 검은색 글자의 길이인 4가 정답이 됩니다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <iostream> #include <cstdio> #include <string>   using namespace std;   string str1, str2;   int lcs[1001][1001];   int main() {     string tmp1, tmp2;     cin >> tmp1 >> tmp2;       // LCS 알고리즘을 위해 앞에 '0'을 붙여준다.     str1 = '0' + tmp1;     str2 = '0' + tmp2;       int len1 = str1.size();     int len2 = str2.size();       for (int i = 0; i < len1; i++)     {         for (int j = 0; j < len2; j++)         {             if (i == 0 || j == 0)             {                 lcs[i][j] = 0;                 continue;             }               // 현재 비교하는 값이 서로 같다면, lcs는 + 1             if (str1[i] == str2[j])                 lcs[i][j] = lcs[i - 1][j - 1] + 1;               // 서로 다르다면 LCS의 값을 왼쪽 혹은 위에서 가져온다.             else             {                 if (lcs[i - 1][j] > lcs[i][j - 1])                     lcs[i][j] = lcs[i - 1][j];                 else                     lcs[i][j] = lcs[i][j - 1];             }         }     }       /*     // 검증 코드     for (int i = 0; i < len1; i++)     {         for (int j = 0; j < len2; j++)             cout << lcs[i][j] << " ";         cout << endl;     }     */       cout << lcs[len1-1][len2-1] << endl;       return 0; } //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus