BOJ 9251: LCS 찾기
글쓴이: HDNua / 작성시간: 금, 2014/12/26 - 7:17오후
문제 링크 - https://www.acmicpc.net/problem/9251
printf로 찍어보니 매번 각각의 LCS는 잘 찾아내는 것 같은데
시간 초과도 아니고 아예 틀렸다고 나오니 어느 부분에 문제가 있는지 궁금합니다.
a에 대해 lcs, b에 대해 lcs를 각각 구하고 두 lcs의 길이를 비교해서 풀었는데 틀렸네요..
어떤 입력에서 오류가 나는지 알 수 있을까요?
이 질문은 Baekjoon Online Judge 질문 게시판에 먼저 올렸다가 답변이 없어서 올리는 것입니다.
#include <stdio.h>
#define MAX_BUFFER_LEN 1001
int main(void) {
char a[MAX_BUFFER_LEN] = "";
char b[MAX_BUFFER_LEN] = "";
char lcs1[MAX_BUFFER_LEN] = "";
char lcs2[MAX_BUFFER_LEN] = "";
char *ap, *bp, *lp;
int prev;
int len1, len2;
scanf("%s %s", a, b);
lp = lcs1;
for (ap=a, prev=0; *ap; ++ap) {
for (bp=b+prev; *bp; ++bp) {
if (*ap == *bp) {
*lp++ = *bp;
prev = bp - b + 1;
// printf("%s\n", lcs1);
break;
}
}
}
len1 = lp - lcs1;
lp = lcs2;
for (ap=b, prev=0; *ap; ++ap) {
for (bp=a+prev; *bp; ++bp) {
if (*ap == *bp) {
*lp++ = *bp;
prev = bp - a + 1;
// printf("%s\n", lcs2);
break;
}
}
}
len2 = lp - lcs2;
printf("%d", (len1 < len2) ? len2 : len1);
return 0;
}Forums:
LCS의 의미를 생각해보면 두 LCS의 비교는 의미가
LCS의 의미를 생각해보면 두 LCS의 비교는 의미가 없습니다.
처음 LCS만 가지고 문제를 해결할 수 있습니다.
그러나 구현이 잘못된 것으로 보이는군요.
LCS의 의사코드나 예제를 잘 살펴보시길 바랍니다.
답변 감사합니다.
아무도 답글을 안 달아서 서운하던 참이었습니다. ㅎㅎ
처음 보는 개념이다보니 틀렸는 모양이네요. 다시 한 번 봐야겠습니다.
저는 이렇게 생각했습니다.
$ echo "MJYAUZ MZJAWXU" |
둘 다 4가 나와야겠지요.
a에 대한 lcs라는 것은 의미가 없습니다.
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
아하 문장의 최대 길이를 찾지 않았군요
답변 감사합니다. 다시 한 번 도전해보겠습니다.
저는 이렇게 생각했습니다.