문제

문제 링크

문제 접근

  • 이전 LCS를 점화식을 이용해서 풀었다면 이 문제는 그리 어려운 문제가 아니다.
  • 점화식의 경우의 수를 나눠보자.
  • 먼저 각 문자열의 해당하는 변수(x, y, z)가 문자열 끝에 다달았을 때는 0을 반환한다.
  • 그리고 이미 dp값이 정해진 길을 갈 때면 그 dp값을 반환한다.
  • a[x] = b[y] = c[z]라면 1을 더하고 x++, y++, z++ 해준다.
  • 그 외에는 x++한 경우, y++한 경우, z++한 경우로 쭉쭉 뻗어나가며 최종 값을 리턴하도록 한다.

코드

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int an, bn, cn, dp[101][101][101];
char a[101], b[101], c[101];

int find_cnt(int x, int y, int z){
    if(x == an || y == bn || z == cn)return 0;
    int &ret = dp[x][y][z];
    if(ret != -1)return dp[x][y][z];
    ret = max(max(find_cnt(x + 1, y, z), find_cnt(x, y + 1, z)), find_cnt(x, y, z + 1));
    if(a[x] == b[y] && b[y] == c[z])ret = max(ret, 1 + find_cnt(x + 1, y + 1, z + 1));
    return ret;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> a >> b >> c;
    memset(dp, -1, sizeof(dp));
    an = strlen(a), bn = strlen(b), cn = strlen(c);
    printf("%d", find_cnt(0, 0, 0));
}

느낀점

  • LCS 잘가라.