[ C++ 백준 1062 ] 가르침

백트래킹 복습할 겸 문제를 풀어보았다.

 

시간 초과로 인해 계속 수정하느라 원래 코드와는 일부분 바뀌긴 했으나

시간 초과가 났던 이유는 이 부분 때문이었다.

 

i = 0 부터 시작하면 시간초과가 난다.

당연한 부분인데 당연히 i = idx라고 적어놓은 줄 알고 30분을 날렸다. ㅎ.ㅎ

 

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

vector<string> vec;
bool visited[26];
int answer = 0;
int N, K;

int CanReadNum()
{
	int value = 0;
	for (int i = 0; i < N; ++i)
	{

		string str = vec[i];
		bool check = true;
		for (int j = 0; j < str.length(); ++j)
		{

			if (visited[str[j] - 'a'] == false)
			{
				check = false;
				break;
			}

		}

		if (check)
			value++;

	}

	return value;
}

void backTracking(int idx, int size)
{

	if (size == K)
	{
		answer = max(answer, CanReadNum());

		if (answer == N) 
		{
			cout << N << '\n';
			exit(0);
		}
	}
	else
	{
		for (int i = idx; i < 26; ++i)
		{
			if (visited[i])
				continue;

			visited[i] = true;
			backTracking(i, size + 1);
			visited[i] = false;
		}
	}



}


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

	//antic
	visited['a' - 'a'] = true;
	visited['n' - 'a'] = true;
	visited['t' - 'a'] = true;
	visited['i' - 'a'] = true;
	visited['c' - 'a'] = true;

	cin >> N >> K;

	string inputStr;
	for (int i = 0; i < N; ++i)
	{
		cin >> inputStr;
		vec.push_back(inputStr.substr(4, inputStr.length() - 8));

	}

	if (K < 5)
	{
		cout << "0";
		return 0;
	}

	K = K - 5;
	backTracking(0, 0);
	cout << answer;

	return 0;

}