글 읽기 - 백트래킹으로 풀리긴 하는데 다른 풀이좀 알려주세요

juhongkim2 6년 전 0

백트래킹으로는 100ms안으로 해결이 안나올거 같아서요...

다른방법은 뭐가 있을까요?

chogahui05 6년 전 0

최악의 경우에는 (26-5)C10 = 352,716인데요.

백트래킹 해도 100ms 안에 나오는데. 안 나오시는 경우에는 다른 문제가 있으실 거 같네요.

예를 들어서, 시간 복잡도 앞에, 문자열 길이만큼이 곱해진다던지..

거기에 set을 초기화 하기 위해서 memset류 함수를 호출하시거나 하면. 26도 곱해지시겠죠.

음.. 혹시

특정 알파벳만을 배웠을 때, 이 단어를 읽을 수 있느냐. 없느냐를 어떻게 검사하셨나요?

예를 들어서 ANTAXYTNMOOTICA라는 단어가 있습니다.

학생들이 ACINTXZ를 배웠습니다. 이 경우에, ANTAXYTNMOOTICA라는 단어를 학생들이 읽을 수 있느냐 없느냐를

어떻게 검사하셨나요?

juhongkim2 6년 전 0

단어 읽는게 가능한지 여부는 비트연산으로 처리했습니다.

어디에서 문제가 생긴걸까요?

#include <stdio.h>

int N,K,len,to_learn[60];
char word[60][20];

int Max(int n1, int n2)
{
	if(n1>n2)
		return n1;

	return n2;
}

int Solve(int choose, int alph, int learned)
{
	int i,res=0;

	if(choose>K || choose>26)
		return 0;

	if(choose==K){
		res=0;
		for(i=0;i<N;i++){
			if((to_learn[i]&learned)==to_learn[i])
				res++;
		}

		return res;
	}

	for(i=alph;i<26;i++){
		if((learned&(1<<i))==0)
			res=Max(res,Solve(choose+1,i+1,learned|(1<<i)));
	}

	return res;
}

int main()
{
	int i,j;

	scanf("%d %d",&N, &K);
	K-=5;

	for(i=0;i<N;i++){
		scanf(" %s", word[i]);

		len=-1;
		while(word[i][++len]);

		for(j=0;j<len;j++){
			if(word[i][j]=='a' || word[i][j]=='n' || word[i][j]=='t' || word[i][j]=='i' || word[i][j]=='c')
				continue;
			to_learn[i]|=(1<<(word[i][j]-'a'));
		}
	}

	if(K<0)
		printf("0\n");
	else
		printf("%d\n",Solve(0,0,0));

	return 0;
}

chogahui05 6년 전 1

필요 없는 경우까지 백트래킹을 하는 게 문젠거 같네요.

실제로 아래와 같은 데이터를 주는 경우에

2600번이 21번째 줄 if문에 걸립니다. 2600이라.. 어떻게 나온 것일까요?

K는 8이였고요. 5를 빼서 3이 되었습니다.

26개 중에서, 서로 다른 3개를 택하는 가짓수는 26C3 = 26*25*24/6 = 2600이 나옵니다.

분명한 건

ant

act

와 같은 것도 탐사했다는 거고요. 답은 맞게 나왔습니다.

이건 이미, acint를 set에서 빼 놓았기 때문이지요. 다만. 백트래킹 과정에서 a, c, i, n, t를 거르지 못했다는 게 문제겠지요.

이들을 포함하는 sub는 보나 마나 없을 텐데 말이죠.

/*
5 8
antarctica
antahellotica
antacartica
antaxyztica
antaicetica
*/

juhongkim2 6년 전 0

아...감사합니다

a,c,i,n,t는 모든 단어에 공통으로 들어가있어서 빼고 생각하면 될 줄 알았는데

백트래킹에서 걸러내지를 못하나보네요

chogahui05 6년 전 0

31번째 줄과 32번째 줄을 보면

learned한 글자에 특정한 글자가 포함되지 않는 경우만 거르고 있습니다.

처음에 learned한 글자는 0이므로, 모든 글자를 안 배웠다고 처리한 건데요. 사실.. a/c/i/n/t는 이미 빼 놓은 글자이고...

set에도 항상 포함이 안 되는 것이니.. 넣을 필요도 없을 거에요.

그렇지 않는다면, 최악의 경우 26C13이 되어서 1040만 즈음이 나오겠지요. 35만과는 30배 차이가 납니다.

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

문제

문제

출처

ICPC

백트래킹으로 풀리긴 하는데 다른 풀이좀 알려주세요

juhongkim2 6년 전 0

chogahui05 6년 전 0

juhongkim2 6년 전 0

chogahui05 6년 전 1

juhongkim2 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말