https://www.acmicpc.net/problem/9251
LCS (Longest Common subsequence, 최장 공통 부분 수열) 문제
- 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제
풀이 과정
- 예제에서 주어진 ACAYKP 와 CAPCAK를 예로 하면, 첫 입력인 ACAYKP에서 A를 먼저 고르고 CAPCAK의 왼쪽에서부터 하나씩 A와 일치하는지 비교하고, 다음은 C를 고르고 CAPCAK의 왼쪽에서부터 하나씩 C와 일치하는지를 비교하는 식으로, 연속해서 일치하는 횟수를 dp라는 배열에 저장하는 것을 반복한다.
- 다시 말해, 주어진 예제의 입력들을 string 타입의 s1, s2로 각각 선언해주고, s1의 길이 만큼, 그리고 s2의 길이 만큼의 2중 for문을 돌면서 s1과 s2가 같아지는 시점에서 현재 dp값에서 +1 한 값을 다음 인덱스의 dp에 저장해주고, s1과 s2가 다를 때에는, 인접하는 이전 인덱스의 값들의 최대값으로 갱신하도록 해준다.
- 그렇게 생성된 dp배열의 마지막 인덱스가 답이 된다.
#include <iostream>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;
int dp[1001][1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
string s1, s2;
cin >> s1 >> s2;
for (int i = 0; i < s1.length(); i++)
{
for (int j = 0; j < s2.length(); j++)
{
if (s1[i] == s2[j])
dp[i+1][j+1] = dp[i][j] + 1;
else
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
}
}
cout << dp[s1.length()][s2.length()] << endl;
return 0;
}