[백준] 9251 LCS / DP (C++)

문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

.
.
풀이

2차원 배열을 활용해야하는 dp 문제다.
처음에 투포인터로 세볼까 헤매다가 다른 사람의 아이디어를 참고하였다.

문자가 다를 경우 이 문자로 인해 달라지는 것이 없기에,
바로 이전 값이나 이전 문자가 현재 길이까지 왔을 때 중 큰 값을 취하고

문자가 같을 경우에는
이전 문자, 이전 자리(왼쪽 대각선 위)의 최대값에 1을 더해준다.

확실히 dp의 핵심은 갱신해주는 데이터를 어떻게 설정하느냐에 있는 듯!

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

int dy[1001][1001];

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

	string s1;
	string s2;
	cin >> s1 >> s2;	

	for (int i = 1; i <= s2.size(); i++)
	{
		for (int j = 1; j <= s1.size(); j++)
		{
			// 두 문자열의 해당 문자가 같으면 -> 계산을 1,1 부터 시작하다보니 문자열에서는 1을 빼주고 있다.
			if (s2[i - 1] == s1[j - 1])
			{
				// 이전 줄, 이전 문자의 최고 길이에 1을 더해 자신을 추가해준다.
				dy[i][j] = dy[i - 1][j - 1] + 1;
			}
			// 해당 문자가 다르면
			else
			{
				// 현재 문자 자리까지 비교했을 때의 이전 줄의 값
				// 바로 전 문자까지 비교한 이번 줄의 값 중에 큰 것 선택
				dy[i][j] = max(dy[i - 1][j], dy[i][j - 1]);
			}
		}
	}	
	cout << dy[s2.size()][s1.size()];
	return 0;
}