[코드업] 2699 - 사투리

GSHS의 K모씨는 서울에서 태어났음에도 불구하고 대구에서 자라났기 때문에 사투리를 사용한다. 

이 때문에 학교친구들은 K모씨에게 장난을 칠 때 사투리로 장난을 치는데 K모씨는 사투리와 서울말이 그렇게 다르지 않다는 것을 친구들에게 알리고 싶다. 

그래서 K모씨는 주어진 사투리와 서울말의 subsequence(연속되는 부분 순서)의 최대 값을 구하려 한다.

이를 구하는 프로그램을 작성하시오.

* 참고 : subsequence란 원래 순서에서 일부 몇 개를 지운 순서를 의미한다.

예를 들어 abcdefg 라는 순서가 있다면 이 순서의 부분순서는

abcdefg, adeg, efg, ag 등이 있다.

하지만 ba와 같이 순서가 바뀐 것은 부분순서가 아니다.

그리고, abcde, bace 의 최대 공통 부분순서는
ace 또는 bce 가 된다. 따라서 위 두 순서의 최대 공통 부분순서의 길이는 3이다.

입력

첫 줄에 길이가 N이하인 사투리가 공백 없이 주어진다.
둘째 줄에 길이가 N이하인 서울말이 공백 없이주어진다.
(사투리와 서울말은 모두 알파벳으로 이루어져 있다)

[입력값의 정의역]
1 <= N <= 1000

출력

공통부분순서의 최대 길이를 출력하라.

입력 예시 

sicohwkdfjxo
wocibhxs

출력 예시

3

---

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

string A, B;
vector<vector<int>> dp;
int LCS(int a, int b){
	if(a == A.size() || b == B.size()) return 0;
	
	int& ret = dp[a][b];
	if(ret != -1) return ret;
	
	if(A[a] == B[b])
		return ret = 1 + LCS(a + 1, b + 1);
	else
		return ret = max(LCS(a + 1, b), LCS(a, b + 1));
}

int main(){
	cin >> A >> B;
	dp.resize(A.size());
	for(int i = 0; i < A.size(); i++){
		dp[i].resize(B.size(), -1);
	}
	cout << LCS(0, 0);

	return 0;
}