풀이
dp[i][j] = a[1~i]와 b[1~j]의 LCS 값
dp[i][j] = max(d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j]))
코드
#include <stdio.h>
#include <algorithm>
char a[1111], b[1111];
int i, j, d[1111][1111];
int main() {
scanf("%s\n%s", a + 1, b + 1);
for (i = 1; a[i]; i++) for (j = 1; b[j]; j++)
d[i][j] = std::max({ d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j]) });
printf("%d", d[i-1][j-1]);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이