9252번: LCS 2

풀면서 막혔던 부분

LCS의 길이 를 구하는 것은 문제가 없었다. 이전에도 풀었던 문제였기 때문에 같은 방식으로 LCS의 길이 를 구했다. 그러나 문제는 LCS의 길이를 구한 이후 그 문자열을 다시 구하는것 이었다. 처음에는 0,0 의 인덱스에서 출발하여 저장된 값이 증가하는 부분들을 체크한 후 그 위치를 출력했으나 예외가 있었다. 그래서 DP배열의 끝부분에서 출발하여 구하니 풀 수 있었다.

코드

시간 : 4 ms

메모리 : 5816 KB

#include<bits/stdc++.h>

int main()
{
	char str1[1001];
	char str2[1001];
	char res[1001];
	int dp[1001][1001];

	for(int i=0;i<1001;i++){
		str1[i] = 0;
		str2[i] = 0;
		dp[i][0] = 0;
		dp[0][i] = 0;
	}

	scanf("%s",str1);
	scanf("%s",str2);

	int i;
	int j;
	j = -1;
	int max = -1;
	while(str2[++j]){
		i = -1;
		while(str1[++i]){
			if (str2[j] == str1[i])
				dp[j+1][i+1] = dp[j][i] + 1;
			else
				dp[j+1][i+1] = (dp[j][i+1] > dp[j+1][i]) ? dp[j][i+1] : dp[j+1][i] ;
			max = (max < dp[j+1][i+1]) ? dp[j+1][i+1] : max;
		}
	}
	printf("%d\\n",max);
	int idx = 0;
	while(i && j){
		if(dp[j][i] == dp[j-1][i]){
			j--;
		}
		else if(dp[j][i] == dp[j][i-1]){
			i--;
		}
		else{
			res[idx] = str1[i-1];
			i--;
			j--;
			idx++;
		}
	}
	while(res[--idx])
		printf("%c",res[idx]);
}