BaekJoon 1062번: 가르침(C++)

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

1062번: 가르침

풀이법

1) 들어온 문자열을 전처리하지 않고 바로 백트래킹을 실시 했을 때 바로 시간 초과가 났던 문제이다.

2) 알파벳 소문자만 입력 값으로 들어오므로 넣을 수 어떤 것이 현재 들어온 것들인지 표기 하기 위해 26개짜리 visited 배열을 만든 후 a,n,t,c,i를 미리 넣어 주었다.

3) 이후 들어온 값들은 "anta"로 시작하고 "tica"로 끝나므로 이 부분들을 substring 함수를 활용하여 제거한 후 a,n,t,i,c, 외에 다른 문자들만 최종 처리할 배열에 넣어 주었다.

4) 이후 k개에 맞게 백트래킹을 실시하여 가능한 최대 문자를 설정해 주었다.

5) 전처리를 진행한다는 점에서 가장 흥미롭기도 했지만 어려웠던 문제여서 추후에 다시 풀어 보기에도 좋은 문제일 듯 싶다.

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

int n, k;
bool visited[26];
vector<string> vec;
int ans = 0;
void checkString()
{
	int cnt = 0;
	for (int i = 0; i < vec.size(); i++)
	{
		bool check = true;
		for (int j = 0; j < vec[i].size(); j++)
		{
			if (!visited[vec[i][j]-'a'])
			{
				check = false;
				break;
			}
		}
		if (check == true)
			cnt++;
	}
	ans = max(ans, cnt);
}
void backtracking(int index, int cnt)
{
	if (cnt == k)
	{
		checkString();
		return;
	}
	for (int i = index; i < 26; i++)
	{
		if (visited[i])//이미 방문한 건 제낀다.
			continue;
		visited[i] = true;
		backtracking(i, cnt + 1);
		visited[i] = false;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	visited['a' - 'a'] = true;
	visited['n' - 'a'] = true;
	visited['t' - 'a'] = true;
	visited['i' - 'a'] = true;
	visited['c' - 'a'] = true;
	if (k < 5)
	{
		cout << "0"; return 0;
	}
	else if (k == 26) {
		cout << n << endl;
		return 0;
	}
	for (int i = 0; i < n; i++)
	{
		string s; cin >> s;
		int length = s.size()-8;
		s = s.substr(4, length);
		string str = "";
		for (int j = 0; j < s.size(); j++)
		{
			if (!visited[s[j] - 'a'])
			{
				str += s[j];
			}
		}
		vec.push_back(str);//필요한 것만 넣었다.
	}
	k = k - 5;
	backtracking(0, 0);
	cout << ans;
}