문제

문제 링크

문제 접근

  • 그렇게 힘들게 풀던 것을 점화식을 이용하니 엄청나게 수월하게 풀려버렸다.
  • 점화식을 이용해서 a[i]와 b[j]가 같은 경우에만 점수를 더한다.
  • 같지 않다면 x를 키우는 길과 y를 키우는 길, 두개로 나눠서 점화식을 이어간다.
  • 이 때 이미 값을 구해본 길을 가게 된다면 그 값을 이용하고 더 나아가지 않는다!

LCS 문자열 찾기

  • 디피값을 다 업데이트 했다면 lcs를 찾아서 출력해줘야한다.
  • i와 j가 같은 값을 찾아서 출력하고 i++, j++해준다.
  • 같지 않은 경우에는 dp값이 i + 1, j와 같은지 i, j + 1과 같은지 비교해서 그쪽으로 다시 점화식을 이어간다.

코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int an, bn, dp[1001][1001];
char a[1001], b[1001];
int find_cnt(int x, int y){
    if(x == an || y == bn)return 0;
    int &ret = dp[x][y];
    if(ret != -1)return ret;
    ret = max(find_cnt(x, y + 1), find_cnt(x + 1, y));
    if(a[x] == b[y]) ret = 1 + find_cnt(x + 1, y + 1); 
    return ret;
}
void find_lcs(int x, int y){
    if(x == an || y == bn)return;
    if(a[x] == b[y]){
        printf("%c", a[x]);
        find_lcs(x + 1, y + 1);
    }
    else if(dp[x + 1][y] == dp[x][y])find_lcs(x + 1, y);
    else find_lcs(x, y + 1);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> a >> b;
    memset(dp, -1, sizeof(dp));
    an = strlen(a), bn = strlen(b);
    printf("%d", find_cnt(0, 0));
    find_lcs(0, 0);
}

느낀점

  • 묵은 체증이 가셨다. LCS 2 잘가라.