[C++] 백준 9251 LCS

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string x, y;
int dp[1001][1001];

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

	getline(cin, x);
	getline(cin, y);

	for (int i = 1; i <= x.length(); i++)
	{
		for (int j = 1; j <= y.length(); j++)
		{
			if (x[i - 1] == y[j - 1])	//0~length까지 x[i]번째와 y의[j~length]번째들이 같나 확인
				dp[i][j] = dp[i - 1][j - 1] + 1;	//같으면 전ij번째의 길이에 + 1해줌
			else
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);	
			//같지 않으면 현재 확인중인 x글자와 y의 j-1번째글자의 비교했던 길이와 
			//전에 확인했던 x글자와 현재의 글자의 비교한 크기를 비교하여 현재x와y를 비교한 값에 넣는다.
		}
	}

	cout << dp[x.length()][y.length()];
}

 

이런 길이를 구하는 문제에서는 쌓아가는 느낌이 많은듯하다.

풀이

1. 현재 x[i-1]와 비교하고있는 y[j-1]가 같으면 전 dp에 +1 한값을 현재 값에 넣는다. (1씩 계속 쌓아넣는다.)

2. 현재 x[i-1]와 비교하고있는 y[j-1]가 다르면 현재 확인중인x글자와 y의 j-1번째글자의 비교했던 길이와 
전에 확인했던 x글자와 현재의 글자의 비교한 크기를 비교하여 현재x와y를 비교한 값에 넣는다.