[백준][1062번] 가르침

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

1062번: 가르침

 

풀이과정 (완전탐색)

 

1. 가르칠 글자의 갯수가 4개 이하이면 0개의 단어를 배우게 된다.  남극의 단어는 anta로 시작하여 tica로 끝나게 되어 총 5개의 기본 글자를 요구하기 때문이다.

 

2. 26개의 알파벳을 모두 가르칠 경우 남극의 모든 단어를 사용 할 수 있다. 바로 N을 답으로 출력하면 된다.

 

3. 1번, 2번 경우가 아니라면 anta, tica에 대한 처리를 한 후 나머지 배울 단어를 정리한다.

anta, tica를 사용하여 substr으로 사잇값을 처리 한 후 배울 수 있는 단어를 중복되지 않게 찾아 learnWord에 저장한다.

 

4. 이 후 완전탐색을 이용하여 배울 수 있는 글자 수 만큼을 중복되지 않게 탐색한다.

 

소스코드(c++)

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int N, K; //N 남극의 단어갯수, K개의 글자
char map[26];
int maxVal = 0;
string learnWord;
vector<string> v;
void init() {
	//anta, tica 처리
	map['a' - 'a'] = 1;
	map['n' - 'a'] = 1;
	map['t' - 'a'] = 1;
	map['i' - 'a'] = 1;
	map['c' - 'a'] = 1;
}

void checkMaxWord()
{
	int result = 0;
	for (int i = 0; i < v.size(); i++) {
		bool notFindWord = false;
		for (int j = 0; j < v[i].length(); j++) {
			if (!map[v[i][j] - 'a']) {
				notFindWord = true;
				break;
			}
		}
		if (!notFindWord) {
			result++;
		}
	}
	if (maxVal < result) {
		maxVal = result;
	}
}

void solution(int idx, int depth)
{
	if (depth + 5 >= K || depth >= learnWord.length()) {
		checkMaxWord();
		return;
	}

	for (int i = idx; i < learnWord.length(); i++) {
		map[learnWord[i] - 'a'] = 1;
		solution(i + 1, depth + 1);
		map[learnWord[i] - 'a'] = 0;
	}
}

int main()
{
	scanf("%d %d", &N, &K);
	if (K <= 4) {
		printf("0\n");
		return 0;
	}
	else if (K == 26) {
		printf("%d\n", N);
		return 0;
	}
	init();
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		str = str.substr(4, str.length() - 8);
		v.push_back(str);
		for (int j = 0; j < str.length(); j++) {
			if (learnWord.find(str[j]) == string::npos && map[str[j] - 'a'] == 0) {
				learnWord += str[j];
			}
		}
	}
	solution(0, 0);
	printf("%d\n", maxVal);
}