백준 1062번: 가르침 (비트마스크)

[문제 링크]

1062번: 가르침

---

https://onlytrying.tistory.com/34?category=808917

4달전 완전탐색을 공부할 때 한번 푼적이 있는 문제였다.

 

알파벳이 a~z 까지 총 26개 존재하기 때문에 32bit인 int형의 2진수로 a~z 까지 알파벳을 배웠는지 안배웠는지 여부를 표현할 수 있다.

 

따라서 비트마스크를 사용할 수 있다는 것을 알 수 있으며, 이를 사용하여 더 효율적인 알고리즘으로 재구현하였다.

 

핵심은 입력받은 단어에 포함된 알파벳을 OR 연산을 통해 int형 변수 word 에 저장함으로써

배운 알파벳의 정보를 가지고 있는 learn과 AND 연산하여 가능 불가능 여부를 O(1) 에 확인할 수 있다는 것이다.

---

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

int learn, word[50];

int max(int a, int b) { return a > b ? a : b; }

int DFS(int start, int N, int K, int learning)
{
	int ret = 0;

	if (learning == K)
	{
		for (int i = 0; i < N; i++)
			if ((word[i] & learn) == word[i]) 
				ret++;

		return ret;
	}

	for (int i = start; i < 26; i++)
	{
		if ((learn & (1 << i)) == 0)
		{
			learn |= (1 << i);
			ret = max(ret, DFS(i + 1, N, K, learning + 1));
			learn &= ~(1 << i);
		}
	}

	return ret;
}

int main(void)
{
	learn |= 1 << ('a' - 'a');
	learn |= 1 << ('c' - 'a');
	learn |= 1 << ('i' - 'a');
	learn |= 1 << ('n' - 'a');
	learn |= 1 << ('t' - 'a');

	int N, K;
	cin >> N >> K;

	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;

		for (int j = 0; j < str.length(); j++)
			word[i] |= (1 << (str[j] - 'a'));
	}
		
	if (K < 5 || K == 26)
		cout << (K == 26 ? N : 0) << endl;
	else
		cout << DFS(0, N, K, 5) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 134 day