글 읽기 - 9251번 LCS를 찾는 문제입니다.

hdnua 9년 전 0

printf로 찍어보니 매번 각각의 LCS는 잘 찾아내는 것 같은데

시간 초과도 아니고 아예 틀렸다고 나오니 어느 부분에 문제가 있는지 궁금합니다.

a에 대해 lcs, b에 대해 lcs를 각각 구하고 두 lcs의 길이를 비교해서 풀었는데 틀렸네요..

어떤 입력에서 오류가 나는지 알 수 있을까요?

#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;
}

Nada 9년 전 4

bcdefgha

acdefghb

가 1이 나오네요.

hdnua 9년 전 0

답변 감사합니다. 다른 글에 비해 하도 댓글이 안 달려서 뭐 잘못한 게 있나 싶었어요 ㅎㅎ

hdnua 5년 전 10

3년만에 다시 찾아와서 제 질문을 보고 웃고 갑니다. :)

eric00513 4년 전 0

Nada님 반례를 넣으니 제 소스도 해결이 되는군요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

9251번 LCS를 찾는 문제입니다.

hdnua 9년 전 0

Nada 9년 전 4

hdnua 9년 전 0

hdnua 5년 전 10

eric00513 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말