BOJ 9251 (LCS)

• 문제
  LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
  
  예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
  
  
• 입력
  첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
  
  
• 출력
  첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char c1[1001];
char c2[1001];
int dp[1001][1001];
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

int main()
{
	fast_io();
	string s1, s2;
	cin >> s1 >> s2;
	for (int i = 0; i < s1.size(); i++)
	{
		c1[i + 1] = s1[i];
	}
	for (int i = 0; i < s2.size(); i++)
	{
		c2[i + 1] = s2[i];
	}

	for (int i = 1; i <= s1.size(); i++)
	{
		for (int j = 1; j <= s2.size(); j++)
		{
			if (c1[i] == c2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	cout << dp[s1.size()][s2.size()];
	return 0;
}

    문제의 조건을 보고 처음엔 2중 반복문으로 구현 가능할거라 생각했는데 방법이 떠오르지 않았다.
알고리즘 분류를 보니 DP를 이용하는 문제였다. (최대, 최소, 최장 등의 단어가 나오면 DP를 의심해봐야 겠다)

문자열을 2개만 입력받기 때문에 메모제이션 기법을 이용하기 위한 2차원 DP배열을 만들었다.
row -> 방향의 문자와 column 방향의 문자가 같으면 이전까지의 최장 수열인 dp[i-1][j-1]에 1을 더해주고 같지 않다면 위쪽과 촤측 값중 큰 수를 넣어주면 된다.
      같을때 : dp[i-1][[j-1]+1
      다를때 : max(dp[i-1][j],dp[i][j-1])

이전에 풀었던 평범한 배낭 문제와 접근 방법이 유사한데 바로 캐치하지 못했다...

시간 복잡도 : O(N^2)