[백준] 9251번 - 동적계획법 LCS

int main()
{
	cin >> A >> B;

	for (int a = 0; a<A.size(); a++)
	{
		for (int b = 0;b<B.size(); b++)
		{
			int x = b + 1, y = a + 1;
			if (A[a] == B[b])
				cache[y][x] = 1 + cache[y-1][x-1];
			else
				cache[y][x] = max(cache[y-1][x],cache[y][x-1]);
		}
	}
	cout << cache[A.size()][B.size()];
}

동적계획법 문제를 푸는데 표까지는 잘 세웠는데 점화식을 도출하는 과정에서 살짝 잘못 세워서 못 풀었다.

 

cache[y][x]는 A문자열의 y번째 문자까지, B문자열의 x번째 문자까지 고려했을 때 LCS(최장 공통 부분수열)길이다.

A문자열의 y번째 문자(고려하는 문자열의 마지막 문자)와 B의 x번째 문자(고려하는 문자열의 마지막 문자)가 같다면

이 문자들을 빼고 계산한 LCS에 1을 더하면 될 것이다. 

즉, if(A[a]==B[b]) 일 때 cache[y][x] = 1 + cache[y-1][x-1]

그리고 마지막 문자들이 같지 않다면 LCS에 A[y]와 B[x]가 함께 들어가는 경우는 존재하지 않기 때문에 A문자열의 마지막 문자를 빼고 비교하는 경우, B문자열의 마지막 문자를 빼고 비교하는 경우 중 큰 경우가 cache값이 될 것이다.

즉, cache[y][x] = max(cache[y-1][x], cache[y][x-1]);

 

풀이를 이해하는데 아래 영상을 참조했다.

https://www.youtube.com/watch?v=EAXDUxVYquY