글 읽기 - 문제에서 배제되는 경우의 수

kokorin 9년 전 0

제가 짠 소스는

첫번째 문장 두번째 문장에 해당하는 배열을 만들어서

세번째 문장에 있으면 1을 넣고

1, 2배열의 0이 있으면 false 나오게 만들었거든요?

근데 틀렸다고 나오길래 제가 배제한 경우가 있나요??

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
main(){
	char A[201];
	char B[201];
	char C[402];
	int sum=0;
	int i,j,a;
	int d=0;
	int *bufferA;
	int *bufferB;
	int yes=1;
	int count=1;
	int T;
	scanf("%d",&T);
	for(a=0; a<T; a++){
	scanf("%s %s %s",A,B,C);
	sum+=strlen(A)+strlen(B);
	if(sum==strlen(C)){
	bufferA=(int*)malloc(sizeof(int)*strlen(A));
	bufferB=(int*)malloc(sizeof(int)*strlen(B));
		for(i=0; i<strlen(A);i++){
			bufferA[i]=0;
		}
		for(i=0; i<strlen(B);i++){
			bufferB[i]=0;
		}
		
		for(j=0; j<strlen(A); j++){
			for(i=d; i<strlen(C); i++){
				if(bufferA[j]==0 && A[j]==C[i]){
					bufferA[j]=1;
					d=i+1;
					break;
				}
			}
		}
	
		d=0;
		for(j=0; j<strlen(B); j++){
			for(i=d; i<strlen(C); i++){
				if(bufferB[j]==0 && B[j]==C[i]){
					bufferB[j]=1;
						d=i+1;
						break;
				}
			}
		}
			
		d=0;
			for(j=0; j<strlen(A); j++){
				if(bufferA[j]==0) yes=0;
		}
				for(j=0; j<strlen(B); j++){
				if(bufferB[j]==0) yes=0;
		}
}
else yes=0;
		if(yes==1){
			printf("Data set %d: yes\n",count);
			count++;
		}
		else if(yes==0){
			printf("Data set %d: no\n",count);
			count++;
		}
	yes=1;
	free(bufferA);
	free(bufferB);
	sum=0;
	}
}

yukariko 9년 전 0

cat cat caatct

의 경우 no가 답인데 yes를 출력하네요.

그리고 for문 조건문에 strlen을 사용하면 시간복잡도가 매 반복마다 O(n)이 붙기 때문에 좋지 않습니다.

아마 답이 맞더라도 시간초과를 받을것 같군요..

변수로 따로 빼서 판별하시는것이 좋습니다.

kokorin 9년 전 0

흠 차라리 확인하는 c배열에 다가

A와 B를 거꾸로 가면서 체크하라는

말씀이신가요??

yukariko 9년 전 1

거꾸로 갈 필요는 없습니다.

길이를 변수로 따로 빼면 매번 0번처럼 strlen을 호출하지 않아도 된다는 의미였구요

소스로 나타내보면 1번과 같이 되겠네요.

문자열의 경우 2번같은 경우도 가능합니다.

//0번
for(int i=0;i<strlen(a);i++);

//1번
int len = strlen(a);
for(int i=0;i<len;i++);

//2번
for(int i=0;a[i];i++);

kokorin 9년 전 0

거꾸로말고 그대로하면요

첫번째 단어 : cat
두번째 단어 : tree
세번째 단어 : catrtee
이부분에서 걸리는데요??
<cat>

c	a	t	r	t	e	e
1	1	1	0	0	0	0

<tree>

c	a	t	r	t	e	e
1	1	1	0	1	0	0

이런식으로 되서 원레 yes인데 거꾸로 체크안하면 이런식으로 되서 no가 나와요..

yukariko 9년 전 1

제가 말씀드린것은 strlen 을 조건문 내에서 사용하면 안된다는 것입니다.

실제 답을 구현하는 알고리즘과는 연관없는 말이었습니다.

저같은 경우는 dp를 이용해서 해결했는데 다른방법은 모르곘네요..

kokorin 9년 전 0

예 알겠습니다 ㅎㅎ 동적계획법 문제였군요 ,.,ㅠㅠ

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

문제

문제

출처

ICPC

문제에서 배제되는 경우의 수

kokorin 9년 전 0

yukariko 9년 전 0

kokorin 9년 전 0

yukariko 9년 전 1

kokorin 9년 전 0

yukariko 9년 전 1

kokorin 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말