알고리즘/문제 풀이
9251번: LCS
Themion
2021. 12. 28. 15:00
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
두 문자열 A와 B에 대해, A[a]와 B[b]까지의 LCS의 길이 lcs[a][b]를 구했다고 하자. 이 때 lcs[a + 1][b + 1]은 A[a + 1] == B[b + 1]일 때 lcs[a][b] + 1이고, 그렇지 않다면 lcs[a + 1][b]와 lcs[a][b + 1] 중 최댓값이다.
#include <cstdio>
#define MAX_LEN 1000
short max(short a, short b) { return a > b ? a : b; }
int main() {
// A, B: 입력받을 두 문자열
char A[MAX_LEN + 1], B[MAX_LEN + 1];
// a, b: A와 B를 탐색하기 위한 인덱스
int a, b;
// len[a + 1][b + 1]: A[0:a]와 B[0:b]의 LCS
short len[MAX_LEN + 1][MAX_LEN + 1] = {{ 0, }};
// A와 B를 입력받는다
scanf("%s\n%s", A, B);
// A와 B에 대해 동적 계획법으로 LCS를 구한다
for (a = 0; A[a]; a++) for (b = 0; B[b]; b++)
len[a + 1][b + 1] = max(len[a][b] + (A[a] == B[b]),
max(len[a + 1][b], len[a][b + 1]));
// 구한 LCS의 최댓값을 출력
printf("%hd\n", len[a % 2][b]);
return 0;
}