BOJ 백준 9251 LCS <dp, LCS>

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

< LCS >

 이 문제는 두 문자열을 받아와서 공통돤 최장 수열을 찾아 그것이 몇 개의 알파벳으로 이루어져 있는 지 출력해주는 문제이다.

예제 입력 1 

ACAYKP
CAPCAK

예제 출력 1 

4

 예제 입력을 보면 ACAYKP 와 CAPCAK를 비교하는데 이 입력의 답은 ACAYKP / CAPCAK으로 ACAK, 4를 출력해주면 된다.

하나의 수열을 두고 LCS를 구하는 문제는 풀어보았지만, 두 문자열을 가지고 공통된 최장 문자열을 찾는 것은 풀기 힘들었다.

https://www.youtube.com/watch?v=P-mMvhfJhu8&t=335s

위 링크의 유투브 영상을 참고했는데 정말 쉽게 잘 설명해주어서 보자마자 문제를 풀 수 있었다.

문제와 풀이가 단순하면서 재미있었다. 다만, 백준에서는 공통된 문자열의 길이만 출력하도록 하게 했지만

유투브 영상 뒤에서 공통된 문자열이 무엇인지 알 수 있는 방법을 소개시켜주었기 때문에 이 후에 공통된 문자열을

출력해주는 알고리즘도 구현해보아야 겠다.

#include <iostream>
#include <string>
#define SIZE 1010

using namespace std;

int dp[SIZE][SIZE];

inline int MAX(int a, int b) { return a > b ? a : b; }

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

	string s1, s2;

	cin >> s1 >> s2;	

	int s1Size = s1.length();
	int s2Size = s2.length();

	for (int i = 1; i <= s1Size; ++i)
	{
		for (int j = 1; j <= s2Size; ++j)
		{
			if (s1[i - 1] == s2[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[s1Size][s2Size] << '\n';

	return 0;
}