★ [Brute Force - 비트마스크] 가르침

예제 입력 1

3 6

antarctica

antahellotica

antacartica

예제 출력 1

2

 

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

1062번: 가르침

- 모든 단어가 anta로 시작하고 tica로 끝나므로, a/n/t/i/c는 기본으로 배운것으로 처리하여 시간복잡도를 줄인다.

 

- 읽을 수 있는 단어를 셀 때, 각각의 단어가 무엇인지 순서가 어떤지 중요한게 아니라, 그 단어에 속한 알파벳을 알고있냐의 여부이므로 모두 저장하지 않고 비트마스크로 해당 단어에 어떤 알파벳이 존재하는지만 저장하여 시간복잡도를 줄인다.

 

- 비트마스크로 처리한 경우에도, 이미 배운 알파벳의 경우는 다음으로 넘어가지 않게 하여 재귀 함수 타는 횟수를 줄여야한다.

 

- 알파벳을 배운상태로 처리하고 다시 원상복구 할 필요가 없는 이유는 int teach변수로 넘겨주므로 call by value에 의해 값이 복사가 되어 그 함수 내에서만 사용되며 원본을 해치지 않기 때문이다. 

 

#include <stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))

const int MAX_WORD_COUNT = 50;

int N, K;
int word[MAX_WORD_COUNT];

bool wordCounter[26];
int wordCount = 0;

int go(int start, int cnt, int teach)
{
	if (cnt == K || cnt >= wordCount)
	{
		int result = 0;

		for (int i = 0; i < N; i++)
		{
			if ((word[i] & ((1 << 26) - 1 - teach)) == 0)
				result++;
		}

		return result;
	}

	int maxResult = 0;

	for (int i = start; i < 26; i++)
	{
		if (i == ('a' - 'a') ||
			i == ('n' - 'a') ||
			i == ('t' - 'a') ||
			i == ('i' - 'a') ||
			i == ('c' - 'a')) continue;

		if (teach & (1 << i)) continue;
		maxResult = MAX(maxResult, go(i + 1, cnt + 1, (teach | (1 << i))));
	}

	return maxResult;
}

int main(void)
{
	scanf("%d %d", &N, &K);

	for (int i = 0; i < N; i++)
	{
		char input[256];
		scanf("\n%s", input);

		int idx = 0;

		while (input[idx] != '\0')
		{
			word[i] |= (1 << (input[idx] - 'a'));

			wordCounter[input[idx] - 'a'] = true;
			idx++;
		}
	}

	for (int i = 0; i < 26; i++)
	{
		if (wordCounter[i]) wordCount++;
	}

	if (K < 5)
	{
		printf("0\n");
	}
	else
	{
		int teach = (1 << ('a' - 'a')) |
			(1 << ('n' - 'a')) |
			(1 << ('t' - 'a')) |
			(1 << ('i' - 'a')) |
			(1 << ('c' - 'a'));

		K -= 5;
		printf("%d\n", go(0, 0, teach));
	}

	return 0;
}