BOJ 17218, 비밀번호 만들기
ProblemSolving ·이 문제는 LCS(최장 공통 부분 수열)문제입니다.
풀이
기본 LCS 알고리즘을 이용하였습니다.
특이점으로는 dp배열을 pair로 선언하여 first에는 LCS의 수,
second에는 LCS 문자를 저장하였습니다.
맨 앞의 문자부터 비교하여 끝까지 비교하였으며,
문자가 같을 때는 그 문자를 더한 값을 저장하고,
문자가 다를 때는 그 전에 더 큰 값을 저장한다.
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
string a, b, ans;
pair<int,string> dp[42][42];
int main()
{
cin >> a >> b;
int ai = a.size();
int bi = b.size();
for (int i = 1; i <= a.size(); i++) {
for (int j = 1; j <= b.size(); j++) {
if (a[i - 1] == b[j - 1]) {
dp[i][j].first = dp[i - 1][j - 1].first + 1;
dp[i][j].second = dp[i - 1][j - 1].second + a[i - 1];
}
else {
if (dp[i][j - 1].first > dp[i - 1][j].first) {
dp[i][j].first = dp[i][j - 1].first;
dp[i][j].second = dp[i][j - 1].second;
}
else {
dp[i][j].first = dp[i-1][j].first;
dp[i][j].second = dp[i-1][j].second;
}
}
}
}
cout << dp[ai][bi].second;
return 0;
}