[9252] LCS2

[9252] LCS2 : http://boj.kr/9252

### DP -Track ### (참고 : https://kks227.blog.me/221028710658)

< 소스코드 >

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
 
struct P { int ret, si; };
 
char s[1001], t[1001];
int d[1001][1001];
char a[1001];
 
stack<P> st;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lcs2(int si, int ti)
{
    int ret = 0; 
 
    if(si < 0 || ti < 0) return 0;
    if(d[si][ti] != -1) return d[si][ti];
 
    if(s[si] == t[ti]) {
        ret = lcs2(si-1, ti-1)+1;
        st.push((P){ret, si});
    }
    else {
        ret = max(lcs2(si-1, ti), lcs2(si, ti-1));
    }   
    return d[si][ti] = ret;
}
 
int main()
{
    int sLen=0, tLen=0;
    scanf("%s%s", s, t);
 
    while(s[sLen]) sLen++;
    while(t[tLen]) tLen++;
 
    memset(d, -1, sizeof(d));
 
    int ans = lcs2(sLen-1, tLen-1);
    printf("%d\n", ans);
 
    while(!st.empty()) {
        if(st.top().ret == ans) {
            a[--ans] = s[st.top().si];
        }
        st.pop();
    }
    puts(a);
}

>> 아이디어는 부분문제의 답을 통해 역으로 그 답을 끼워 맞춘다.

>> 테스트 케이스는 아래와 같다.

ACAYKP

CAPCAK

>> 위 테케에 대한 아웃풋은 아래와 같다.

4

ACAK

>> 위 코드의 경우, 스택 st의 ret 에는 3 4 2 1 3 2 1 가 저장이 된다. 

>> 맨 처음 정답에 해당하는 4일때의 si, 그다음 작은 숫자인 3일때의 si, ...

>> 이렇게 문자를 거꾸로 저장한 다음 출력하면 답이 된다.