글 읽기 - 이 문제 어떻게 2초안에 들어오는 건가요??

san9407 5년 전 0

밑에 있는 질문검색글에서

djm03178님의 답변을 보고 26!/16!에서 26C10으로 바꿨더니 맞추긴 했는데

26C10 = 5311735 가지에

N = 50개 들어오고 7글자 봐야하면

5311735 * 50 * 7 이면 1859107250이라는 어마어마한 계산량이 나오는데

어떻게 2초안에 들어오는지 궁금합니다.

break가 있긴있어서 조금 줄긴할텐데..

break가 있을시 시간복잡도 계산법을 몰라서요 ㅠㅠ,

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int INF = 1000000000;

int N, K;
char str[51][16];
bool check[26];
int maxx;
void go(int cnt,int x)
{
	if (cnt == K - 5)
	{
		int tmp = 0;
		for (int j = 0; j < N; j++)
		{
			bool flag = false;
			int size = strlen(str[j]);
			for (int k = 0; k < size; k++)
			{
				if (!check[str[j][k] - 'a'])
				{
					flag = true;
					break;
				}
			}
			if (!flag)
				tmp++;
		}
		maxx = max(maxx, tmp);
		return;
	}
	for (int i = x; i < 26; i++)
	{
		if (check[i])
			continue;
		check[i] = true;
		go(cnt + 1,i+1);
		check[i] = false;
	}
}

int main()
{
	scanf("%d %d", &N, &K);
	if (K < 5)
	{
		puts("0");
		return 0;
	}
	check['a' - 'a'] = check['c'-'a'] = check['t'-'a'] = check['i'-'a'] = check['n'-'a'] = true;
	for (int i = 0; i < N; i++)
	{
		scanf("%s", str[i]);
	}
	go(0,0);
	printf("%d\n", maxx);
	return 0;
}

djm03178 5년 전 1

제가 그 때 계산을 잘못한 것 같습니다. 최악의 경우는 K=15일 때 a, c, i, n, t 5개를 제외한 21자 중 10개를 뽑는 경우인 것 같습니다.

san9407 5년 전 0

아 그렇네요 ㅋㅋ

답변 감사합니다!

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

문제

문제

출처

ICPC

이 문제 어떻게 2초안에 들어오는 건가요??

san9407 5년 전 0

djm03178 5년 전 1

san9407 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말