[BOJ/C++] 1062 가르침

문제

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

풀이

• 단어가 "anta"로 시작하고, "tica"로 끝난다 => 공통으로 포함되는 a n t i c는 반드시 학습시켜야 한다.

• K가 5 미만이면 0 출력하고 바로 종료

• vector에 접두사, 접미사 빼고 가운데 부분만 넣음

• dfs로 K-5개만큼 알파벳 뽑으면서 최댓값을 갱신해나가면 된다.

  • 뽑을 수 있는 알파벳이 더 있으면 remain 감소시키면서 계속 재귀 호출
  • 재귀 호출이 끝나면 다시 alpha[i]를 false로 원위치 시켜줘야한다.
    
    
  • remain이 0이면 vector 탐색하면서 현재 뽑은 알파벳으로 읽을 수 있는 단어 개수를 셈
  • 이 때, 읽을 수 있는 단어 개수가 N과 같아지면 바로 종료시켜서 시간을 줄인다.

    💡
    exit(0);
    프로그램 즉시 종료
    return;
    현재 호출된 dfs함수만 종료되고, 상위 호출로 돌아감
    
    따라서, 시간복잡도를 줄이기 위해서는 exit(0);을 사용해 불필요한 탐색이 발생하지 않도록 해야한다.

• bool alpha[26];을 이용해서 T/F 체크해주기
  
  

dfs함수 호출 흐름

ex1) (0,3) -> (1,2) -> (3,1) -> (4,0) -> (5,0) -> ⋯ -> (25,0) -> (4,1) -> (5,0) -> (6,0) -> ⋯
ex2) (0,1) -> (1,0) -> (2,0) -> (3,0) -> ⋯ -> (25,0)

코드

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

using namespace std;

int N, K;
int ans;
vector<string> v;
bool alpha[26];

void dfs(int idx, int remain) {
	if (remain == 0) {
		int cnt = 0;
		for (int i = 0; i < v.size(); i++) {
			string elem = v[i];
			bool flag = true;
			for (int j = 0; j < elem.size(); j++) {
				char ch = elem[j];
				if (!alpha[ch - 'a']) {
					flag = false;
					break;
				}
			}
			if (flag) cnt++;
		}
		ans = max(ans, cnt);
		if (ans == N) {
			cout << N << '\n';
			exit(0);
		}
	}

	for (int i = idx; i < 26; i++) {
		if (alpha[i])	continue;
		alpha[i] = true;
		dfs(i, remain - 1);
		alpha[i] = false;
	}
}

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

	string str;

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> str;
		v.push_back(str.substr(4, str.length() - 8));
	}

	if (K < 5) {
		cout << 0 << '\n';
		return 0;
	}

	alpha[0] = true; //a
	alpha[2] = true; //c
	alpha[8] = true; //i
	alpha[13] = true; //n
	alpha[19] = true; //t

	dfs(0, K - 5);
	cout << ans << '\n';

	return 0;
}