BOJ - 1062번 가르침 (C++)

문제 출처: https://www.acmicpc.net/problem/1062

문제 난이도

Gold 4

문제 접근법

DFS를 사용했다.
앞 뒤 네글자는 공통이라고 볼 때, K가 5보다 아래면 아무런 단어도 볼 수 없으므로 0.
K가 26이면 모든 알파벳을 배우는 거기 때문에 모든 단어를 볼 수 있으므로 N.
그 외는 하나씩 알파벳을 false, true 해가며 check하며 풀었다.

통과 코드

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

using namespace std;

bool alpha[26];
int res = -1;

void dfs(int a, int K, int cnt, vector<string> words) {
	if (cnt == K) {
		int ch = 0;
		for (int i = 0; i < words.size(); i++) {
			string str = words[i];
			bool flag = true;
			for (int j = 0; j < str.size(); j++) {
				if (!alpha[str[j] - 'a']) {
					flag = false;
					break;
				}
			}
			if (flag) ch++;
		}
		res = max(res, ch);
		return;
	}
	for (int i = a; i < 26; i++) {
		if (alpha[i]) continue;
		alpha[i] = true;
		dfs(i, K, cnt + 1, words);
		alpha[i] = false;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, K;
	cin >> N >> K;
	vector<string> words;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		words.push_back(str.substr(4));
	}
	alpha['a' - 'a'] = true;
	alpha['n' - 'a'] = true;
	alpha['t' - 'a'] = true;
	alpha['i' - 'a'] = true;
	alpha['c' - 'a'] = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 4; j++) {
			words[i].pop_back();
		}
	}
	if (K < 5) {
		cout << 0;
	}
	else if (K == 26) {
		cout << N;
	}
	else {
		dfs(1, K - 5, 0, words);
		cout << res;
	}
	return 0;
}

피드백

시간 초과가 자꾸 나서 이거 안나게 하려고 코드 계속 손 본듯..
특히 중간에 문자열이 읽을 수 있는 문자열이 맞는지 체크하려고 할 때, 따로 함수로 빼서 처리했는데 시간초과 났다. 그래서 그냥 다 dfs 안에 넣어버림..