dp 백준 9251 LCS

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

9251번: LCS

이 문제는 두개의 문자열 중 동일한 부분수열 중 가장 긴 부분수열의 개수를 구하는 문제이다. 

 

하나의 문자열을 베이스로 하나하나 동일한지 비교하며 표를 채워 나가면된다.

 

if (letter1[i] == letter2[j] ) 

이전 문자열 단계(이전 문자열의 최장 길이)에서 하나씩 증가하면 된다. 

결국 ACAYKP와 CAPCAK는 K의 이전 ACAY와 CAPCA의 최장길이에서 +1을 하면된다. 

 

동일하지 않다면 

이전의 dp 개수 또는 위의 dp 개수 중 큰 수를 선택하여 입력해주면된다. 

결국 ACAYKP와 CAPCAK는 ACAY와 CAPCA는 서로 끝이 다르다 이와 같은 경우에는 Y, A중 더 긴 길이의 값을 집어 넣으면 된다. 

 

백준예제의 경우 아래와 같이 표가 나오며 점화식을 구할 수 있다. 

#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;

int dp[1003][1003];

int main(){
	char letter1[1003];
	char letter2[1003];

	scanf("%s", letter1);
	scanf("%s", letter2);

	int length1 = strlen(letter1);
	int length2 = strlen(letter2);

	for(int i = 1; i <= length1; i++){
		for(int j = 1; j <= length2; j++){
			if(letter1[i-1] == letter2[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			else{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}

	printf("%d", dp[length1][length2]);
}