백준 1958번 LCS 3

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

http://jaimemin.tistory.com/383과 비슷한 문제였습니다.

LCS 2는 공통문자열까지 출력을 해야했기 때문에 어떻게 본다면 LCS 3보다 더 어려운 문제라고 할 수 있습니다.

LCS 3은 아래와 같이 7가지 경우의 수를 고려하면 쉽게 풀 수 있는 문제였습니다.

1. s1만 인덱스 증가할 경우

2. s2만 인덱스 증가할 경우

3. s3만 인덱스 증가할 경우

4. s1과 s2만 인덱스 증가할 경우

5. s1과 s3만 인덱스 증가할 경우

6. s2와 s3만 인덱스 증가할 경우

7. s1[idx1], s2[idx2], s3[idx3] 모두 같은 문자이기 때문에 전부 인덱스 증가할 경우

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100;

 

string s1, s2, s3;

int cache[MAX][MAX][MAX];

 

int LCS(int idx1, int idx2, int idx3) //s1,s2, 그리고 s3의 인덱스 전달 받음

{

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

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

                 return 0;

 

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

        if (result != -1)

                 return result;

 

        //총 7가지 경우의 수

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

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

        //3. s3만 인덱스 증가했을 경우

        result = max(LCS(idx1 + 1, idx2, idx3), max(LCS(idx1, idx2 + 1, idx3), LCS(idx1, idx2, idx3 + 1)));

        //4. s1과 s2 인덱스 증가했을 경우

        //5. s1과 s3 인덱스 증가했을 경우

        //6. s2와 s3 인덱스 증가했을 경우

        result = max(max(result, LCS(idx1 + 1, idx2 + 1, idx3)), max(LCS(idx1 + 1, idx2, idx3 + 1), LCS(idx1, idx2 + 1, idx3 + 1)));

        //7. s1, s2, s3 모두 인덱스 증가했을 경우

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

        return result;

}

 

int main(void)

{

        cin >> s1 >> s2 >> s3;

       

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

       

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

        return 0;

}

개발환경:Visual Studio 2017

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