[1958번] LCS 3

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

위의 링크를 통해 확인해보면 알겠지만, 위의 링크에서는 2차원적인 LCS에 대해 설명을 하고 있다.

이번 문제는 3차원 LCS문제이다.

2차원 LCS에 대해 제대로 이해하고 있다면

x, y, z축을 생각하며 x,y 였을때에 z에 대한 조건들만 더 추가해주면 쉽게 통과 할 수 있다.

3중 for문이지만, string의 제한이 100이기에 O(100^3)에 해결이 가능하다.

소스 코드 : 

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 64 65 66 67 68 69 70 71 72 73 74 75 76

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

Crocus