백준 - 가르침 (c++)

문제 :

SW Expert Academy

문제설명

1. 조합문제이다. 21개의 조합 중(anta tica 제외) 제한시간이 1초는 중복제거를 한다면 충분히 가능한 시간이다.

 

알고리즘

1. 남극언어의 특징인 접두사와 접미사는 무조건 읽어야만한다.(anta tica)

2. 21개의 알파벳과 K - 5 만큼 조합한다.

3. 조합된 원소를 이용해 읽을 수 있는 단어를 체크한다.

 

주의사항

1. 남극언어 필수 알파벳 5개보다 가르칠 수 있는 개수가 적으면 읽을 수 있는 단어는 0이다.

2. DFS 함수 구현 시 idx 변수를 통해 했던 조합은 중복 제거를 해야한다. 안그러면 시간초과 발생

 

구현

bool alpabet[26];
int N, K;
string word[50];
int maxValue;

bool checkWord(string str) {

	for (int i = 4; i < str.size()-4; i++)
	{
		if (!alpabet[str[i] - 'a'])
			return false;
	}
	return true;
}

void DFS(int cnt,int idx)
{
	if (cnt == K)
	{
		int wCount = 0;
		for (int i = 0; i < N; i++)
		{
			if (checkWord(word[i]))
				wCount++;
		}


		//printf("\nWcnt = %d\n",wCount);
		if (maxValue < wCount)
			maxValue = wCount;
		return;
	}


	for (int i = idx; i < 26; i++)
	{
		if (!alpabet[i])
		{
			alpabet[i] = true;
			DFS(cnt + 1,i);
			alpabet[i] = false;
		}
	}
}

//atinc r
int main()
{
	scanf("%d %d", &N, &K);


	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		word[i] = s;
	}

	if (K < 5)
		printf("0");
	else
	{
		alpabet['a' - 'a'] = 1;
		alpabet['n' - 'a'] = 1;
		alpabet['t' - 'a'] = 1;
		alpabet['i' - 'a'] = 1;
		alpabet['c' - 'a'] = 1;
		K -= 5;
		DFS(0,0);
		printf("%d", maxValue);
	}
}