1062 가르침

https://www.acmicpc.net/problem/1062

1062번: 가르침

 

(풀이)

글자 K개를 가르쳤을떄 N개의 단어들 중에 읽을 수 있는 최대의 갯수를 출력하는 문제.

문제만 보면 난이도가 왜 골드인지 모르는데. 시간복잡도를 구하다보면 시간초과가 나는 부분이 생긴다.

 

 

1)글자 K개를 가르치는 부분의 시간복잡도를 구해보면

 모든 알파벳은 26개이고, 이 26개 단어 하나 두개 사용하여 체크하면 2^26 = 약6710만 갯수이고

 

2) 읽을 수 있는 단어인지 검사를하면 단어는 최대50개 , 중간의 스펠링을 체크하는 경우의수 @ 까지하면

  6710만 * 50 * @ 로 @를 하기전에도 이미 30억을 넘어가는순간 시간 초과가 나버린다.

 

3) 시간 복잡도를 줄이는 방법.

 3-1) 문제의 'anta' 로 시작해서 'tica' 로 끝나면 이 스펠링은 총 [a,n,t,i,c] 5개로 26개중 5개를 제외한 

21개를 체크할 수 있다.

 

 3-2) 순서는 상관하지않고 K개를 뽑는것이다. 한마디로 26개 알파벳중에 K개를 뽑는것이니

       26Combination K 의 최악의경우 26C13 이것도 1000만을 넘기기 떄문에

       3-1)의 방법을 응용하여 26-5 Combination K = 21CK 를해보자 

 

 3-3) K를 제외하고 21개의 진부분집합 - 공집합 (공집합 :  K<5 인 경우, 어떤 단어도 읽지못함 )
        진부분집합 2^21 -1개 (진부분집합 : K가 26인경우 전체를 읽을 수 있음, 이 두경우를 뺼수 있다)

        2^21 - 2 개는 209만 7천으로 약 210만개다, 

 

 3-4) 문자를 검사할때 스펠링 하나라도 false가 나오면 못읽는 단어니 string내에서 char 스펠링 체크루프를

       빠져나온다. 이론적 시간복잡도가 아닌 효율을 조금 높일 수 있음.

 

(코드)

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;

bool check[26];
void go(int cnt, int index);
int N, K;
int ans = 0;
vector<string> word_list;
int main(void)
{
	cin >> N >> K;
	if (K < 5)
	{
		cout << 0 << '\n';
		return 0;
	}
	if (K == 26)
	{
		cout << N << '\n';
		return 0;
	}
	word_list.assign(N, "");
	for (int i = 0; i < N; ++i)
	{
		cin >> word_list[i];
		word_list[i].erase(word_list[i].begin(), word_list[i].begin() + 4);
		word_list[i].erase(word_list[i].end() - 4, word_list[i].end());
	}
	check['a' - 'a'] = check['n' - 'a'] = check['t' - 'a'] = check['i' - 'a'] = check['c' - 'a'] = true;

	K = K - 5;
	//go(0,0);
	
	cout << ans << '\n';
	return 0;
}
void go(int cnt, int index)
{
	if (cnt == K)
	{
		string temp;
		int can_read = 0;
		for (int i = 0; i < N; ++i)
		{
			temp = word_list[i];
			bool isRead = true;
			for (int j = 0; j < temp.size(); ++j) //r , c , h , e, l , l ,o , c , a , r
			{
				if (!check[temp[j]-'a']) //알파벳을 배우지 않은경우
				{
					isRead = false;
					break;
				}
			}
			if (isRead) 
				can_read += 1;
		}
		if (can_read > ans)
			ans = can_read;
		return;
	}

	//0~25 : a ~ z;
	for (int i = index; i < 26; ++i)
	{
		if (!check[i])
		{
			check[i] = true;
			go(cnt + 1,i+1);
			check[i] = false;
		}
	}

}