[백준]1062 가르침 c++

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

1062번: 가르침

처음에는 "anta"와 "tica"사이에 등장하는 알파벳들 사이에서 k-5(psb))개를 뽑으려 했다.

근데 만약에 k가 25이고 "anta"와 "tica"사이에 등장하는 단어가 25보다 작다면 if(depth==psb) 조건문에 걸리지 않는다.

그래서 check를 끝까지 다 방문했을 경우에도 wordCount를 호출했었는데 안되었다.

결국 그냥 A~Z까지 psb개를 뽑아서 단어를 읽을 수 있는지 검사했다.

 

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

int N, K;

bool temp[26];
bool check[26];
string s[51];
int psb, cnt, maxN;
int r;
bool visit = false;
void wordCount()
{
	cnt = 0;
	for (int i = 0; i < N; i++)
	{
		if (s[i].length() == 8)
		{
			cnt++;
			continue;
		}
		for (int j = 4; j < s[i].length() - 4; j++)
		{
			if (!check[s[i][j] - 'a'])
			{
				break;
			}
			if (j == s[i].length() - 5)
			{

				cnt++;
			}
		}
	}


}

void backtracking(int depth, int index)
{

	if (depth == psb)//||(r==25&&!visit))
	{

		wordCount();

		if (cnt > maxN)
			maxN = cnt;


		return;
	}
	for (int i = index; i < 26; i++)
	{
		if (!check[i])
		{

			r = i;
			check[i] = true;

			backtracking(depth + 1, i + 1);
			check[i] = false;




		}
	}
}

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

	cin >> N >> K;
	if (K < 5)
	{
		cout << 0;
		return 0;
	}

	int end;

	check['a' - 'a'] = true;
	check['n' - 'a'] = true;
	check['t' - 'a'] = true;
	check['i' - 'a'] = true;
	check['c' - 'a'] = true;

	for (int i = 0; i < N; i++) {
		cin >> s[i];
		end = s[i].length() - 4;


	}
	psb = K - 5;

	//psb개를 뽑기
	backtracking(0, 0);
	cout << maxN;
}

비트마스킹으로 푼것

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

int N, K;

bool temp[26];
int check;
int s[51];
int psb, cnt, maxN;
int r;
bool visit = false;
void wordCount()
{
	cnt = 0;
	for (int i = 0; i < N; i++)
	{
		if ((s[i] & check )== s[i])
			cnt++;
		if (cnt > maxN)
			maxN = cnt;
	}
	return;

}

void backtracking(int depth, int index)
{

	if (depth == psb)//||(r==25&&!visit))
	{

		wordCount();

		if (cnt > maxN)
			maxN = cnt;


		return;
	}
	for (int i = index; i < 26; i++)
	{
		if (!(check&(1<<i)))//방문 안한 경우에
		{

			
			check |= (1 << i);
			backtracking(depth + 1, i + 1);
			check &= ~(1 << i);




		}
	}
}

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

	cin >> N >> K;
	if (K < 5)
	{
		cout << 0;
		return 0;
	}

	int end;

	check |= 1 << ('a' - 'a');
	check |= 1 << ('n' - 'a');
	check |= 1 << ('t' - 'a');
	check |= 1 << ('i' - 'a');
	check |= 1 << ('c' - 'a');

	int num = 0;
	string sTemp;
	for (int i = 0; i < N; i++) {
		cin >> sTemp;
		num = 0;
		for (int j = 4; j < sTemp.length() - 4; j++)
			num |= 1 << (sTemp[j] - 'a');
		s[i] = num;

	}
	psb = K - 5;

	//psb개를 뽑기
	backtracking(0, 0);
	cout << maxN;
}

시간이 많이 절약되었다.