(BOJ, 1062) 가르침

실패코드 : O(2^n) Time Exceed

문자열을 26비트로 저장 + 개수 count를 비트로 연산은 좋았으나 ..

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N, K;
char s[16];
int str[50];
int ans=0;
int cnt;

inline int get_size(int v) {
	int cnt = !!v;
	while (v &= v - 1)cnt++;
	return cnt;
};
void dfs(int index, int val) {
	if (index == N) return;
	if (get_size(val | str[index]) <= K) {
		cnt++;
		if (cnt > ans)ans = cnt;
		dfs(index + 1, val | str[index]);
		cnt--;
	}
	dfs(index + 1, val);
}

int main() {
	scanf("%d %d\n", &N, &K);
	for (register int i = 0; i < N; i++) {
		scanf("%s", s);
		str[i] |= (1 << ('a' - 'a')) | (1 << ('n' - 'a')) | (1 << ('t' - 'a')) | (1 << ('i' - 'a')) | (1 << ('c' - 'a'));
		for (register int j = 0; s[j]; j++) {
			if (s[j] == 'a' || s[j] == 'n' || s[j] == 't' || s[j] == 'i' || s[j] == 'c')
				continue;
			str[i] |= (1 << (s[j] - 'a'));
		}
	}
	cnt = 0;
	dfs(0,0);
	printf("%d\n", ans);
	
	return 0;
}

문자열 50개를 넣을지말지 보다는(여기까지 본인 아이디어)

 

26개 알파벳으로 K개의 알파벳이 채택된다고 했을 때, 각각 케이스에서 문자열이 몇개 들어가는지 체크하여 max를 알아내면 된다. (해답) 최대 26C13 * 50개의 문자열 -> 최대 5억이면 가능

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N, K;
char s[16];
int str[50];
int ans=0;
int check_bit;

int check() {
	int cnt = 0;
	for (register int i = 0; i < N; i++) {
		if (!(str[i] & ~check_bit))cnt++;
	}
	return cnt;
}
void dfs(int depth, int index) {
	if (K - depth > 26 - index) return;
	if (depth == K) {
		int ret = check();
		if (ret > ans) ans = ret;
		return;
	}

	for (register int i = index; i < 26; i++) {
		check_bit |= 1 << index;
		dfs(depth+1, i+1);
		check_bit &= ~(1 << index);
	}
}
int main() {
	scanf("%d %d\n", &N, &K);
	for (register int i = 0; i < N; i++) {

		scanf("%s", s);

		str[i] |= (1 << ('a' - 'a')) | (1 << ('n' - 'a')) | (1 << ('t' - 'a')) | (1 << ('i' - 'a')) | (1 << ('c' - 'a'));
		for (register int j = 0; s[j]; j++) {
			if (s[j] == 'a' || s[j] == 'n' || s[j] == 't' || s[j] == 'i' || s[j] == 'c')
				continue;
			str[i] |= (1 << (s[j] - 'a'));
		}
	}
	dfs(0,0);
	printf("%d\n", ans);
	
	return 0;
}

는 뭔가 느리다.. (400ms )

알고봤더니 조합에서 a n t i c 는 고정이므로 고려할 필요가 없다  21C10 * 50 = 1500만이면 가능

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N, K;
char s[16];
int str[50];
int ans=0;
int check_bit;
int flag[26];

int check() {
	int cnt = 0;
	for (register int i = 0; i < N; i++) {
		if (!(str[i] & ~check_bit))cnt++;
	}
	return cnt;
}
void dfs(int depth, int index) {
	if (depth == K) {
		int ret = check();
		if (ret > ans) ans = ret;
		return;
	}
	for (register int i = index; i < 26; i++) {
		if (i == 'a' - 'a' || i == 'n' - 'a' || i == 't' - 'a' || i == 'i' - 'a' || i == 'c' - 'a') continue;
		if (K - depth > 26 - i) return;
		check_bit |= 1 << i;
		dfs(depth + 1, i + 1);
		check_bit &= ~(1 << i);
	}
}
int main() {
	scanf("%d %d\n", &N, &K);
	for (register int i = 0; i < N; i++) {
		scanf("%s", s);
		for (register int j = 0; s[j]; j++) {
			str[i] |= (1 << (s[j] - 'a'));
		}
	}
	check_bit |= (1 << ('a' - 'a')) | (1 << ('n' - 'a')) | (1 << ('t' - 'a')) | (1 << ('i' - 'a')) | (1 << ('c' - 'a'));
	if (K >= 5) {
		K -= 5;
		dfs(0, 0);
	}
	printf("%d\n", ans);
	
	return 0;
}

결과 : 16ms