풀면서 막혔던 부분
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]);
}
C++
복사
