[백준/Baekjoon] 9252 LCS2 C++ :: Dynamic programming

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

9252번: LCS 2

---

1. Logic

LCS1 문제에서 구현한 것을 반대로 재귀호출을 한 다음 return 하면서 해당하는 문자 값을 출력하는 문제.

 

LCS를 구할 때는 topdown으로 풀었는데 여기서 지나온 경로를 찾으려니 잘 안되어 다른 블로그를 참고하여 bottomup 방식으로 풀이했다

 

지나온 경로를 찾는 원리는 LCS를 구하는 과정에서 str1[s1-1] == str2[s2-1]이면 dp[i][j]=dp[s1-1][s2-1]이 모든 공통 부분 문자열 중 하나이기 때문에 다시 그 칸으로 재귀호출을 한다. 

 

str1[s1-1] != str2[s2-1]의 경우도 LSC를 구할 때 dp배열의 왼쪽값 과 위쪽 값중 최댓값을 취했기 때문에 반대로 문자열을 찾아갈 때도 dp의 왼쪽 혹은 위쪽 중 최대값이 있는 부분으로 다시 재귀 호출을 하여 찾아가면 된다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

string str1, str2;
int dp[1001][1001];
char trace[1001];

void solve() {
    for(int i = 1; i <= str1.length(); i++) {
        for(int j = 1; j <= str2.length(); j++) {
            if(str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else 
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    cout << dp[str1.size()][str2.size()] << "\n";
}

void print(int s1, int s2) {
    if(dp[s1][s2] == 0) return;

    if(str1[s1 - 1] == str2[s2 - 1]) {
        print(s1 - 1, s2 - 1);
        cout << str1[s1 - 1];
    }
    else 
    //LCS를 찾을 때 왼쪽과 위쪽 중 큰 값을 취했기 때문에 역추적 할 때도 큰쪽으로 들어감
    dp[s1-1][s2] > dp[s1][s2-1] ? print(s1 - 1, s2) : print(s1, s2 - 1);
}

int main() {
    memset(dp, 0, sizeof(dp));
    cin >> str1 >> str2;

    solve();

    print(str1.size(), str2.size());
}

 

---

3. Feedback

항상 dp를 topdown으로 풀으려고만 했는데 문제마다 topdown으로 풀어야 쉬운 문제가 있고 bottomup으로 풀어야 쉬운 문제가 있는 것 같다. 이 문제는 역추적에 대해 bottom up으로 풀어야 길을 쉽게 찾을 수 있을 것 같다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐