글 읽기 - 1062

pyoneer 7년 전 0

어느 테스트 케이스에서 틀리는지 잘 모르겠습니다 ㅜㅜ

#include <stdio.h>
#include <string.h>
char str[51][21];
int alp[26] = {-1,-2,-1,-2,-2,-2,-2,-2,-1,-2,-2,-2,-2,-1,-2,-2,-2,-2,-2,-1,-2,-2,-2,-2,-2,-2};
int n,k;
int way = 0;
//a, n, c, t, i



void learn(int depth,int learn_n,int learn_word){
	int i,len;
	int more = 0;
	if(depth == n && learn_n == k-5){
		if(way < learn_word){
			way = learn_word;
		}
		return;
	}
	
	if(depth < n && learn_n <= k-5 && n-depth > way-learn_word){

		len = strlen(str[depth]);
		for(i=0;i<len;i++){
			if(alp[str[depth][i]-97] == -2){
				more++;
				alp[str[depth][i]-97] = depth;
			}
		}
		learn(depth+1,learn_n+more,learn_word+1);
		
		for(i=0;i<26;i++){
			if(alp[i] == depth){
				alp[i] = -2;
			}
		}
		
		if(more != 0)
			learn(depth+1,learn_n,learn_word);
	}
}


int main(){
	char temp[21];
	int i,j,t;
	int alp[26];
	scanf("%d %d",&n,&k);
	for(i=0;i<n;i++){
		scanf("%s",temp);
		t=0;
		for(j=4;j<strlen(temp)-4;j++){
			str[i][t++] = temp[j];
		}
		str[i][t] = '\0';
	}
	if(k>=5){
		learn(0,0,0);
		printf("%d",way);
	}
	else
		printf("0");
	
}

zlzmsrhak 7년 전 1

1. 14번째 줄에서 learn_n <= k-5 여야 합니다.

2. N 제한이 50일 때는 O(2^N) 알고리즘에 커팅으로 시간을 줄인다고 해도 1초 내에 나오기 매우 어렵습니다.

위 풀이보다 더 좋은 방법이 있습니다. 다른 방법을 생각해 보세요.

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

문제

문제

출처

ICPC

1062

pyoneer 7년 전 0

zlzmsrhak 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말