링크
https://www.acmicpc.net/problem/9251
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
풀이
배낭 문제의 알고리즘과 비슷한 LCS(최장 수열) 문제이다.
이차원 배열을 만들고 관행(?)에 따라 인덱스 0번자리에는 모두 0으로 빈 자리로 남겨두고 1번부터 사용한다.
ACAYKP와 CAPCAK를 예시로 들겠다.
첫번째 C와 A는 같지 않으므로 왼쪽 또는 위쪽 중 큰 값을 그대로 가져온다.
두번째 C와 AC에서 같은 부분 C가 나왔으므로 +1 을 해준다.
다음 CA와 ACA를 보겠다.
같은 부분 CA가 나왔는데 이때 C와 AC를 검사한 값에서 +1을 해주어야 한다.
이유는 중복되어 검사될 수 없기 때문이다. 마지막 A가 서로 같아서 값을 올려주는 것이기 때문에 검사에 사용된 두 A를 뺀 값에서 더해주어야한다.
따라서 왼쪽 위 인덱스의 값에서 +1 을 해준다.
다음은 예제의 결과이다.
| 0 | A | C | A | Y | K | P | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| A | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| P | 0 | 1 | 1 | 2 | 2 | 2 | 3 |
| C | 0 | 1 | 2 | 2 | 2 | 2 | 3 |
| A | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
| K | 0 | 1 | 2 | 3 | 3 | 4 | 4 |
코드
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int letter[1001][1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string a, b;
cin >> a >> b;
for (int i = 1; i <= b.length(); i++) {
for (int j = 1; j <= a.length(); j++) {
if (b[i - 1] == a[j - 1]) {
letter[i][j] = letter[i - 1][j - 1] + 1;
}
else {
letter[i][j] = max(letter[i - 1][j], letter[i][j - 1]);
}
}
}
cout << letter[b.length()][a.length()];
return 0;
}
