https://www.acmicpc.net/problem/9251
이 문제의 경우 DP중에 LCS라는 것에 공부해보았으면 풀 수 있는 문제 였다 처음 보고 나서 부분 순서가 아닌 부분수열로 보아서 틀렸었다 이에 LCS 알고리즘에 대해 공부한 푸니 그리 어렵지 않은 문제였다
#include <iostream>
#include <cstring>
using namespace std;
#define max(a, b) (a > b ? a : b)
int LCS[1002][1002];
char str[1003];
char str2[1003];
int main()
{
cin >> str >> str2;
int i, j;
i = 1;
while (i <= strlen(str))
{
j = 1;
while (j <= strlen(str2))
{
if (str2[j - 1] == str[i - 1])
{
LCS[i][j] = LCS[i - 1][j - 1] + 1;
}
else
{
LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
}
j++;
}
i++;
}
printf("%d", LCS[i - 1][j - 1]);
}맨 처음
아래 와 같은 표를 만들준다 만들어 주게 되면 7X7 배열이 될텐데 이는 비교하지 않았을 때 에 대한 값 0을 넣어주기 위함이다.
이에 우리가 각 행 마다 채워넣어줄 것은 각각 행까지의 문자들을 열까지의 문자들과 비교했을 때 최대로 나오는 부분 수열의 크기를 넣어줘야한다 이를 바탕으로 다음 수열의 최댓값을 찾을 것이다
즉 C를 열들의 문자와 비교한다 1행 1열이 0인이유는 C를 A까지 비교했을떄 나오는 부분수열이 없기 떄문이다 그후 C를 A C라는 문자열과 비교했을 때 부분수열로 나온것은 C이니 1 지금 집합 C에서의 부분수열이 1밖에 나올수 없으므로 1만채워주게 된다
그 후 두번째 줄은 C A에서의 부분수열값과 A의 부분수열값을 비교해주게 되는데 C A와 A는 하나의 부분수열 만 공유한다 C A와 A C 도마찬가지이다 C혹은 A만을 공유하기에 1이다 단 이제 C A와 A C A를 비교해주게 되면 현재 C A로 부분수열이 만들어진다 이것은 즉이것은 C만을 비교했을 때 이미 부분수열이 1이었고 그다음 A를 비교했을 때 이부분이 현재 같으므로 이전에 가져왔던 값에 +1을 해주게 된다
그림을 완성 하게 되면
이런식으로 된다 즉 이 문제를 푸는 핵심은 x축으로의 문자열 과 y축으로 문자열을 비교해서 즉 y 인덱스 까지의 수열에서 행의 문자열들과 몇개가 유사한지를 찾는 것이다 이 부분에서 사용되어야 할게 나의 이전에 문자이다 . 예로
A C A 와 C A를 비교했다고 가정하자 이미 C를 검사했을 때 x축의 C 의 이후 문자들에서는 무조건 1개의 부분수열이 발생한다는 의미이고 C A와 검사했을 때 C까지 이미 1인 부분수열이 있었으므로 A를 만났을 때 A의 이전까지의 최대 부분수열의 갯수와 지금 일치한 대각선의 값이 +1되게 하여 증가시키는 것이다 즉 A C 와 C를 비교했을 때 이미 1개의 부분수열이 존재함으로 A C A 와 C A 를 비교했을때 +1을 해주게 되는 것이
결국에 이식의 점화식은
LCS[i][j] = LCS[i - 1][j - 1] + 1;LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);이렇게 2개가 되는데
같은 문자를 발견했을 때는 나의 이전 문자까지 비교했을 때의 최대 부분수열의 구성요소 갯수 +1을 해야함으로 i-1과 j-1인덱스의 값에서 +1을 증가시킨다
반대로 틀릴경우에는 즉 y축에서의 나의 이전의 값을 가져오거나 나까지 비교하기전에 최대 부분수열의 인덱스를 가져오게 된다