[백준/BOJ] 백준 9251번 : LCS

https://www.acmicpc.net/problem/9251

9251번: LCS

input1 문자열의 point1 지점, input2 문자열의 point2 지점에서부터 확인해 나간다

 

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

int cache[1000][1000];
string input1;
string input2;

//input1 문자열의 point1지점, input2 문자열의 point2지점에서 확인해 나간다
int Solve(int point1, int point2)
{
	//범위를 넘어갔을때
	if (point1 >= input1.size())
		return 0;
	if (point2 >= input2.size())
		return 0;

	int& ret = cache[point1][point2];

	//계산한적이 있을때
	if (ret != -1)
		return ret;

	ret = 0;

	//같은 문자일때
	if (input1[point1] == input2[point2])
	{
		ret++;
		ret += Solve(point1 + 1, point2 + 1);
	}

	else
		ret += max(Solve(point1 + 1, point2), Solve(point1, point2 + 1));

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	memset(cache, -1, sizeof(cache));

	cin >> input1;
	cin >> input2;

	cout << Solve(0, 0);

	return 0;
}