9252번 : LCS 2

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

9252번: LCS 2

 

 

이 문제는 다이나믹 프로그래밍 문제이다.

 

 

DP 정의를 잘하면 쉽게 풀 수 있는 문제이다.

 

 

---

 

 

 

두 문자열의 가장 긴 공통된 부분 수열을 찾아야 하는 문제이다.

 

 

 

str1 : ACAYKP

str2 : CAPCAK

 

 

 

이 두 수열에서 가장 긴 공통된 부분 수열을 어떻게 찾을 수 있을까?

 

 

 

만약 가장 긴 공통된 부분 수열이 있다고 가정하면, CAPCAK에서 각 문자는 가장 긴 부분 수열의 마지막 문자가 될 수 있다.

 

 

 

따라서, K부터 시작해서 ACAYKP의 P와 비교를 시작해야 한다.

 

 

 

두 문자열의 인덱스를 비교하면서, 가장 긴 공통된 부분 수열을 찾아야 한다.

 

 

 

만약에, 비교되는 문자가 다르다면, 각 문자열에서 번갈아가며 한 문자를 제외하고 나머지 문자열을 비교해줘야 한다.

 

 

 

만약에, 비교되는 문자가 같다면, 각 문자열에서 동시에 한 문자를 제외하고 나머지 문자열을 비교해주면 된다.

 

 

 

Top-Down식으로 작성해도 되고, Bottom-Up식으로 작성해도 된다.

 

 

 

---

 

 

해설코드(C++).

 

 

 

#include <iostream>
#include <string>
 
using namespace std;
 
 
string dp[1001][1001] = {};
string s1, s2;
string solve(int s1_idx, int s2_idx) {
    //cout << s1_idx << " : " << s2_idx << endl;
    if (s1_idx == -1 || s2_idx == -1)
        return "";
 
    if (dp[s1_idx][s2_idx].size() != 0)
        return dp[s1_idx][s2_idx];
 
    string temp = "";
    if (s1[s1_idx] == s2[s2_idx]) {
        temp = solve(s1_idx - 1, s2_idx - 1) + s1[s1_idx];
    }
    else {
        string t_s1 = solve(s1_idx - 1, s2_idx);
        string t_s2 = solve(s1_idx, s2_idx - 1);
        if (t_s1.size() > t_s2.size())
            temp = t_s1;
        else
            temp = t_s2;
    }
    dp[s1_idx][s2_idx] = temp;
    return dp[s1_idx][s2_idx];
}
 
int main(void) {
    //freopen("input.txt", "r", stdin);
    cin >> s1;
    cin >> s2;
    string result = solve(s1.size() - 1, s2.size() - 1);
    cout << result.size() << endl;
    cout << result << endl;
    return 0;
}