[백준][1062][C++] 가르침

링크

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

1062번: 가르침

해설

반드시 포함되는 anta tica 에 대한 예외처리를 안 하면 시간 초과가 납니다.

혹시 시관 초과가 나서 보러 오셨다면 위의 예외처리를 해보시고 그래도 안되면 보시기 바랍니다.

 

 

간단한 백트래킹 문제입니다.

다만 반드시 포함되는 a c i n t 이 다섯 글자에 대한 예외처리만 하고 백트래킹을 하면 됩니다.

 

해결방법은 다음과 같습니다.

1. a c i n t 가 반드시 포함되어야 하므로 K 가 5 미만이면 0개입니다.

2. 5 이상이면 체크리스트에 a c i n t 를 입력하고 배울 수 있는 개수도 5개 줄입니다.

3. 각 알파벳에 대해 백트래킹을 하면서 브루트포스 알고리즘을 적용시킵니다.

 

저는 시간을 조금이라도 더 줄이려고 비트 마스킹을 이용해서 풀었습니다.

 

코드에 대한 약간의 설명을 드리자면

 

MASK : 이제껏 배운 알파벳들의 위치만 0 입니다.

 

SELECT : 단어들 중 한 번이라도 나온 알파벳들만 1입니다. (즉 배울 필요가 없는 걸 걸러 내는 용도)

 

TABLE은 기본적으로 모두 0으로 초기화돼있고 각 단어별로 해당 알파벳을 배워야 할 경우 해당 자리만 1로 바뀝니다.

 

DFS를 실시하기 전에 a c i n t 을 먼저 다 배우고 실시하는 조건이므로 MASK 에 0 처리

그리고 SELECT 에 이미 배웠으므로 0으로 빼줍니다.

 

그 후 백트래킹을 더 이상 할 수 없다고 판단되면 ( 더 배울 수 있는 단어의 수가 0 이거나 알파벳 끝까지 다 배운 경우)

각 테이블의 단어들과 지금까지 배운 알파벳 (MASK) 를 and 연산 후 ! 하면 읽을 수 있는지 나옵니다.

 

코드

#include <iostream>
using namespace std;

int N, K, BEST = 0;
unsigned int MASK = -1, SELECT = 0;
unsigned int TABLE[50] = { 0, };

void DFS(int _num) {
	for (; _num < 26; ++_num) {
		if (SELECT & 1 << _num)
			break;
	}
	if (K == 0 || _num == 26) {
		int now = 0;
		for (int i = 0; i < N; ++i) {
			if (!(TABLE[i] & MASK)) {
				++now;
			}
		}
		BEST = BEST > now ? BEST : now;
		return;
	}
	--K;
	MASK &= ~(1 << _num);
	DFS(_num + 1);
	MASK |= 1 << _num;
	++K;
	DFS(_num + 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;

	for (int i = 0; i < N; ++i) {
		char inp[16];
		cin >> inp;
		int j = 0;
		while (inp[j]) {
			TABLE[i] |= 1 << inp[j] - 'a';
			++j;
		}
		SELECT |= TABLE[i];
	}

	if (K < 5) {
		cout << '0';
	}
	else {
		unsigned int temp = 532741;
		SELECT &= ~temp;
		MASK &= ~temp;
		K -= 5;
		DFS(0);
		cout << BEST;
	}
	return 0;
}