[BOJ]1062번: 가르침 (c++)

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

1062번: 가르침

 

비트마스크 + 백트랙킹

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int count(vector<int>& words, int mask)
{
	int cnt = 0;
	for (int word : words)
	{
		// word에 mask에 포함되지 않는 비트가 없다면 카운팅
		if ((word & ((1 << 26) - 1 - mask)) == 0)
		{
			++cnt;
		}
	}
	return cnt;
}

int go(vector<int> &words, int left, int mask, int strt)
{
	// 글자를 모두 정하면 : 고른 알파벳으로 읽을 수 있는 단어 개수 반환
	if (left == 0)
	{
		return count(words, mask);
	}

	int max_cnt = 0;
	for (int i = strt; i < 26; ++i)
	{
		// 알파벳 acint 는 다시 고르지 않음
		if ((i == 'a' - 'a' || i == 'c' - 'a' || i == 'i' - 'a'
			|| i == 'n' - 'a' || i == 't' - 'a'))
		{
			continue;
		}

		// i번째 알파벳을 선택하는 경우 최대값
		max_cnt = max(go(words, left - 1, mask | (1 << i), i + 1), max_cnt);
	}

	return max_cnt;
}

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

	// 입력
	int N, K;
	cin >> N >> K;
	vector<int> words(N);
	for (int i = 0; i < N; ++i)
	{
		string word;
		cin >> word;

		for (char c : word)
		{
			words[i] |= (1 << (c - 'a'));
		}
	}

	// 모든 단어가 anta ~ tica로 이루어져 있으므로, 
	// 기본마스크에 acint 포함
	int acint_bits = (1 << 'a' - 'a') | (1 << 'c' - 'a') 
					| (1 << 'i' - 'a') | (1 << 'n' - 'a') 
					| (1 << 't' - 'a');

	// K - 5개의 글자를 골라 읽을 수 있는 최대 단어 개수 출력
	cout << go(words, K - 5, acint_bits, 0);

	return 0;
}

 

 

비트마스크와 백트랙킹을 결합한 문제로는 처음 풀어보았다.

acint를 미리 포함시켜 주면 시간이 매우 절약된다

 

 

 

go 재귀함수를 다음과 같이 알파벳 인덱스 기준으로 잡을 수도 있다

int go(vector<int> &words, int idx, int left, int mask)
{
	if (left < 0)
	{
		return 0;
	}
	if (idx == 26)
	{
		return count(words, mask);
	}

	int sum1 = 0;
	// idx번째 알파벳을 선택하는 경우
	if (!(idx == 'a' - 'a' || idx == 'c' - 'a' || idx == 'i' - 'a' || idx == 'n' - 'a' || idx == 't' - 'a'))
	{
		sum1 = go(words, idx + 1, left - 1, mask | (1 << idx));
	}

	// idx번째 알파벳을 선택하지 않는 경우
	int sum2 = go(words, idx + 1, left, mask);

	return max(sum1, sum2);
}