[C++] 9252번 LCS 2 - DP

#include <stdio.h>
#include <algorithm>
#include <stack>

#define MAX_LEN 1001

using namespace std;

char s1[MAX_LEN], s2[MAX_LEN];  //문자열
int dp[MAX_LEN][MAX_LEN];  //DP
stack<char> s;

void input()
{
    scanf("%s %s", s1, s2);
}

int main()
{
    input();
    
    int i, j;
    for(i=0; s1[i]; i++) {
        for(j=0; s2[j]; j++)
            dp[i+1][j+1]=max({dp[i][j]+(s1[i]==s2[j]), dp[i][j+1], dp[i+1][j]});
    }  //LCS 구하기
    
    printf("%d\n", dp[i][j]);
    if(dp[i][j]) {
        int cnt=dp[i][j];
        while(cnt) {
            if(s1[i-1]==s2[j-1]) {
                s.push(s2[j-1]);
                i--, j--; cnt--;
            }
            else dp[i-1][j]>dp[i][j-1] ? i--:j--;
        }
        while(!s.empty()) {
            printf("%c", s.top()); s.pop();
        }
    }
    return 0;
}

새로운 스킬을 하나 배울 수 있었다. DP에서 나오는 과정을 알고 싶다면 그걸 메모 해놓고 거꾸로 돌아가면 된다는 것이다. 

 

그리고 돌아가는 과정에서 만나는 것들을 스택에 넣고 거꿀로 출력하면 그게 답이 된다. 너무 어렵다....... 솔직히 나에게는

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.