백준 [9251] "LCS"

학교 알고리즘 수업때 학습했던 내용이였다. 하지만 그때 당시에는 이론적인 학습이 주로였기에 LCS(DP)문제를 직접적으로 해결하지는 않았었다. 그런 이유로 LCS라는 이름을 들었을때 해결법이 바로 떠오르지 않았지만 계속 문제를 풀어보니 어느샌가 문제 해결법이 떠올랐다.

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;
int dp[1002][1002] = { 0 };

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    string a, b;

	cin >> a >> b;

	for (int i = 1; i <= a.length(); i++) {
		for (int j = 1; j <= b.length(); j++) {
			if (a[i - 1] == b[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	cout << dp[a.length()][b.length()];

	return 0;

}