https://www.acmicpc.net/problem/9252
- 2월동안 187문제 풀기(지난달 누적 87개) (34/187)
- 쉽게 풀려고, 그냥 부모의 위치랑 문자까지 저장함.
- 근데 그냥 부모 알려주는 정수 하나만 저장해도 될듯
```c++ #include <bits/stdc++.h> using namespace std;
string a, b; struct Node { int val, pa, pb; char c; }; Node dp[1010][1010];
int main() { cin » a » b;
for(int i = 1; i <= a.size(); i++) { for(int j = 1; j <= b.size(); j++) { if(a[i-1] == b[j-1]) dp[i][j] = {dp[i-1][j-1].val+1, i-1,j-1, a[i-1]}; else if(dp[i][j-1].val < dp[i-1][j].val) dp[i][j] = {dp[i-1][j].val, i-1,j, 0}; else if(dp[i][j-1].val >= dp[i-1][j].val) dp[i][j] = {dp[i][j-1].val, i,j-1, 0}; } }
cout « dp[a.size()][b.size()].val « endl;
int x = a.size(), y = b.size(); string ans = “”; while(x && y) { if(dp[x][y].c) ans.push_back(dp[x][y].c); int nx = dp[x][y].pa; int ny = dp[x][y].pb; x = nx, y = ny; } reverse(ans.begin(), ans.end()); cout « ans; }