글 읽기 - 반례를 찾지 못하겠습니다...ㅜㅜ

seonjoo2030 5년 전 1

코드가 지저분해 보일 수 있지만, 그래도 예제 값 잘 나오고, 문자 하나일 때, 그리고

첫번째 문자열의 각각의 문자들에 대해서 두번째 문자열과 비교해 공통 부분 수열을 찾아내도록 했습니다.

예를들어,

ABCD

ERAB

인 경우, 첫 번째 문자열에서 A를 선택하고, 두번째 문자열에서 A로 시작하는 공통 부분 수열을 찾습니다.

그리고, B를 선택하고 다시 두번째 문자열에서 B로 시작하는 공통 부분 수열을 찾습니다.

이렇게 한 후에 각각의 수열을 저장하고 길이도 저장합니다.

마지막에 가장 긴 값을 찾아서 출력하도록 했는데 어떤 반례가 있는 것인지, 아니면 어디를 실수한 것인지 모르겠습니다 ㅜㅜ

#include <stdio.h>
#include <string.h>
char fst[1001];  //첫 번째 입력받는 문자열
char sec[1001]; //두 번째 입력받는 문자열
char res[1001][1001];  // 첫 번째 문자열의 각각 문자에 대한 결과 값 저장
int result[1001];  // 최장 공통 부분 수열의 길이 저장하는 배열

int main()
{
	scanf("%s %s", fst, sec);  // 문자열 입력받음
	int size = strlen(fst);  // 첫번째 문자열의 길이
	int size2 = strlen(sec);  //두 번째 문자열의 길이

	int j = 0;  // 두 번째 문자열의 위치 지정할 변수
	int r = 0;  // 결과 값을 저장하기 위해 배열 위치를 지정할 변수

	for (int t = 0; t < size; t++)
	{
		while (j < size2)
		{
			for (int i = t; i < size; i++)
			{
				for (int k = j; k < size2; k++)
				{
					if (fst[i] == sec[k])  // 첫 번째 문자의 단어와 같은 단어 만나면 
					{
						res[t][r] = fst[i];  // 결과 배열에 저장
						r++;  // 결과 배열의 다음 칸으로 이동
						j = k + 1; // 같은 문자가 나온 위치 다음번 부터 다시 검사하기 위한 설정
						break;
					}
					else if (i == size - 1) // 같은 단어가 없는 경우
						j = size2;  // while문 벗어나기 위한 설정
				}
			}
		}
		result[t] = strlen(res[t]);  // 첫번째 문자열의 각각의 각각의 문자에 대해 찾은 공통 부분 수열의 길이들 저장
		j = 0;  
		r = 0;
	}
	
	int max = result[0];  //가장 긴 최장 공통 수열을 찾기 위한 변수
	int check = 0;
	for (int i = 1; i < size; i++)  // 최대값 찾기
	{
		if (max < result[i])
		{
			max = result[i];
			check = i;
		}
	}
	printf("%d\n", max);  // 갯수 출력
	for (int i = 0; i < max; i++)  // 해당 문자열 출력
		printf("%c", res[check][i]);
	printf("\n");
}

eric00513 5년 전 0

반례입니다.

원래 아래와 같이 출력되야 하는데, 16과 aaaaaaaaaaaaaaaa가 출력됩니다.

// 입력
a aaaaaaaaaaaaaaaa

// 출력
1
a

seonjoo2030 5년 전 1

오 일단 감사합니다.

그 문제 해결했습니다 쓸데없이 while문을 써서 그러더라구요...

근데 그래도 계속 틀렸다고 나옵니다 ㅜㅜ

첫 번째 문자열이 긴 경우, 두번째 문자열이 긴 경우, 다 확인해 봤고, 하나만 입력되었을 때, 그리고 나머지는 동일합니다...ㅜㅜ

#include <stdio.h>
#include <string.h>
char fst[1001];  //첫 번째 입력받는 문자열
char sec[1001]; //두 번째 입력받는 문자열
char res[1001][1001];  // 첫 번째 문자열의 각각 문자에 대한 결과 값 저장
int result[1001];  // 최장 공통 부분 수열의 길이 저장하는 배열

int main()
{
	scanf("%s %s", fst, sec);  // 문자열 입력받음
	int size = strlen(fst);  // 첫번째 문자열의 길이
	int size2 = strlen(sec);  //두 번째 문자열의 길이

	int j = 0;  // 두 번째 문자열의 위치 지정할 변수
	int r = 0;  // 결과 값을 저장하기 위해 배열 위치를 지정할 변수

	for (int t = 0; t < size; t++)
	{
		for (int i = t; i < size; i++)
		{
			for (int k = j; k < size2; k++)
			{
				if (fst[i] == sec[k])  // 첫 번째 문자의 단어와 같은 단어 만나면 
				{
					res[t][r] = fst[i];  // 결과 배열에 저장
					r++;  // 결과 배열의 다음 칸으로 이동
					j = k + 1; // 같은 문자가 나온 위치 다음번 부터 다시 검사하기 위한 설정
					break;
				}
			}
		}
		result[t] = strlen(res[t]);  // 첫번째 문자열의 각각의 각각의 문자에 대해 찾은 공통 부분 수열의 길이들 저장
		j = 0;  
		r = 0;
	}
	
	int max = result[0];  //가장 긴 최장 공통 수열을 찾기 위한 변수
	int check = 0;
	for (int i = 1; i < size; i++)  // 최대값 찾기
	{
		if (max < result[i])
		{
			max = result[i];
			check = i;
		}
	}
	printf("%d\n", max);  // 갯수 출력
	for (int i = 0; i < max; i++)  // 해당 문자열 출력
		printf("%c", res[check][i]);
	printf("\n");
}

eric00513 5년 전 0

@seonjoo2030 나머지는 스스로 해결해 보세요.

eric00513 5년 전 0

죄송합니다 제가 말씀드린 반례는 문제에 어긋나는 반례입니다

seonjoo2030 5년 전 0

아~ 네네 어떤 것 때문에 그러시는지 알겠어요 ㅎㅎ

그리고 반례를 찾은 것 같습니다. 이게

CAPCAK

ACAYKP

CAPCAK

이렇게 순서만 바꿔서 입력해보니까 결과가 다르더군요...ㅜㅜ

그리고 LCS 알고리즘이라고 해서 인터넷에 돌아다니는게 있는데 그런 알고리즘은 따로 공부하고 풀어야 하는건가요?
사실 제가 혼자 공부하는 입장이라 어떤 알고리즘에 대한 공식이 있는 걸 확인하면 약간 멍 해집니다 ㅋㅋ

너무 무턱대고 하는 건 아닌가 하는 생각도 들구요.,..

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

문제

문제

출처

ICPC

반례를 찾지 못하겠습니다...ㅜㅜ

seonjoo2030 5년 전 1

eric00513 5년 전 0

seonjoo2030 5년 전 1

eric00513 5년 전 0

eric00513 5년 전 0

seonjoo2030 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말