포스팅을 너무 오랫동안 안 해서 뭐라도 포스팅하긴 해야겠고.. 이럴 때 제일 만만한 게 PS라서 오랜만에 문제 풀어 올립니다.

은근히 꿀 문제인데 사람들이 적게 푼 문제. DP와 LCS를 이용하면 쉽게 해결이 가능한 문제입니다. LCS는 ‘같으면 같이 전진하고, 다르면 각각 전진한다’로 간단하게 요약할 수 있겠습니다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>

using namespace std;
int dp[1001][1001];
string str1, str2;
int size1, size2;
int solution(int pos1, int pos2)
{
	if (pos1 == size1 || pos2 == size2)
		return 0;
	int& ret = dp[pos1][pos2];
	if (ret != -1)return ret;
	ret = 0;
	if (str1[pos1] == str2[pos2])
		ret = max(ret, solution(pos1 + 1, pos2 + 1) + 1);
	else
		ret = max(ret, max(solution(pos1 + 1, pos2), solution(pos1, pos2 + 1)));
	return ret;
}
int main()
{
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
#endif
	while (cin >> str1 >> str2)
	{
		memset(dp, -1, sizeof(dp));
		size1 = str1.size();
		size2 = str2.size();
		printf("%d\n", solution(0, 0));
	}
}

앞으로 PS도 자주 포스팅 하겠습니다.